0-1 बीएफएस (बाइनरी वेट ग्राफ में सबसे छोटा पथ) सी प्रोग्राम में?

मान लीजिए कि हमारे पास कुछ नोड्स और जुड़े किनारों के साथ एक ग्राफ है। प्रत्येक किनारे में द्विआधारी भार होता है। तो भार या तो 0 या 1 होगा। एक स्रोत शीर्ष दिया गया है। हमें स्रोत से किसी अन्य शीर्ष तक सबसे छोटा रास्ता खोजना है। मान लीजिए कि ग्राफ नीचे जैसा है -

सामान्य बीएफएस एल्गोरिथम में सभी एज वेट समान होते हैं। यहां कुछ 0 हैं और कुछ 1 हैं। प्रत्येक चरण में हम इष्टतम दूरी की स्थिति की जांच करेंगे। यहां हम नोड को स्टोर करने के लिए डबल एंडेड कतार का उपयोग करेंगे। तो हम किनारे के वजन की जांच करेंगे। यदि यह 0 है, तो इसे आगे की ओर धकेलें, अन्यथा पीछे की ओर। आइए बेहतर विचार प्राप्त करने के लिए एल्गोरिदम की जांच करें।

एल्गोरिदम

बाइनरीबीएफएस(src) -

begin
   define dist array to store source to vertex i into dist[i]. Initially fill with infinity
   dist[src] := 0
   insert src into queue Q.
   v := first element from Q, and delete it from queue
   while Q is not empty, do
      for all connected edge e of v, do
         if the weight of v to next of i > dist[v] + weight of v to i weight, then update the weight
            if the weight is 0, then store to front, otherwise back
         end if
      done
   done
   print all distance from dist array
end

उदाहरण

#include<iostream>
#include<vector>
#include<deque>
#define V 8
using namespace std;
struct node {
   int next, weight;
};
vector <node> edges[V];
void binaryBFS(int src) {
   int dist[V];
   for (int i=0; i<V; i++) //initially set as infinity
      dist[i] = INT_MAX;
   deque <int> Q;
   dist[src] = 0; //distance from source to source is 0
   Q.push_back(src);
   while (!Q.empty()) {
      int v = Q.front(); //delete first vertex, and store to v
      Q.pop_front();
      for (int i=0; i<edges[v].size(); i++) {
         //check optimal distance
         if (dist[edges[v][i].next] > dist[v] + edges[v][i].weight) {
            dist[edges[v][i].next] = dist[v] + edges[v][i].weight;
            if (edges[v][i].weight == 0) //0 weight edge is stored at front, otherwise at back
               Q.push_front(edges[v][i].next);
            else
               Q.push_back(edges[v][i].next);
         }
      }
   }
   for (int i=0; i<V; i++)
      cout << dist[i] << " ";
}
void addEdge(int u, int v, int wt) {
   edges[u].push_back({v, wt});
   edges[v].push_back({u, wt});
}
int main() {
   addEdge(0, 1, 0);
   addEdge(0, 3, 1);
   addEdge(0, 4, 0);
   addEdge(1, 2, 1);
   addEdge(1, 7, 0);
   addEdge(2, 5, 1);
   addEdge(2, 7, 0);
   addEdge(3, 4, 0);
   addEdge(3, 6, 1);
   addEdge(4, 6, 1);
   addEdge(5, 7, 1);
   addEdge(6, 7, 1);
   int src = 6;
   binaryBFS(src);
}

आउटपुट

1 1 1 1 1 2 0 1