मान लीजिए हमारे पास कुछ नोड्स और कनेक्टेड एज वाला एक ग्राफ है। प्रत्येक एज का बाइनरी वेट है। इसलिए वेट या तो 0 या 1 होगा। एक सोर्स वर्टेक्स दिया गया है। हमें सोर्स से किसी भी अन्य वर्टेक्स तक सबसे छोटा पथ ढूंढना है। मान लीजिए ग्राफ नीचे जैसा है:
सामान्य BFS एल्गोरिदम में सभी एज वेट समान होते हैं। यहां कुछ 0 हैं और कुछ 1। प्रत्येक चरण में हम इष्टतम दूरी की स्थिति की जांच करेंगे। यहां हम नोड को स्टोर करने के लिए डबल एंडेड क्यू (deque) का उपयोग करेंगे। इसलिए हम एज वेट की जांच करेंगे। यदि यह 0 है, तो इसे फ्रंट पर पुश करें, अन्यथा बैक पर। आइए बेहतर विचार के लिए एल्गोरिदम देखें।
एल्गोरिदम
binaryBFS(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 edges[V];
void binaryBFS(int src) {
int dist[V];
for (int i=0; i Q;
dist[src] = 0; // सोर्स से सोर्स की दूरी 0 है
Q.push_back(src);
while (!Q.empty()) {
int v = Q.front(); // पहला वर्टेक्स डिलीट करें, और v में स्टोर करें
Q.pop_front();
for (int i=0; i dist[v] + edges[v][i].weight) {
dist[edges[v][i].next] = dist[v] + edges[v][i].weight;
if (edges[v][i].weight == 0) // 0 वेट एज को फ्रंट पर स्टोर करें, अन्यथा बैक पर
Q.push_front(edges[v][i].next);
else
Q.push_back(edges[v][i].next);
}
}
}
for (int i=0; i
आउटपुट
1 1 1 1 1 2 0 1
