चौड़ाई पहली खोज (बीएफएस) ट्रैवर्सल एक एल्गोरिदम है, जिसका उपयोग किसी दिए गए ग्राफ़ के सभी नोड्स पर जाने के लिए किया जाता है। इस ट्रैवर्सल एल्गोरिथम में एक नोड का चयन किया जाता है और फिर सभी आसन्न नोड्स को एक-एक करके देखा जाता है। आसन्न सभी शीर्षों को पूरा करने के बाद, यह एक और शीर्षों की जाँच करने के लिए आगे बढ़ता है और अपने आसन्न शीर्षों को फिर से जाँचता है।
प्रतिस्पर्धी कोडिंग में, हमें समस्याओं को बहुत जल्दी हल करना होता है। हम इस एल्गोरिदम को लागू करने के लिए एसटीएल (सी ++ की मानक लाइब्रेरी) का उपयोग करेंगे, हमें कतार डेटा संरचना का उपयोग करने की आवश्यकता है। सभी आसन्न कोने कतार में जोड़ दिए जाते हैं, जब सभी आसन्न कोने पूरे हो जाते हैं, तो एक आइटम को कतार से हटा दिया जाता है और फिर से उस शीर्ष से ट्रैवर्स करना शुरू कर देता है।
ग्राफ़ में कभी-कभी, हमें कुछ चक्र मिल सकते हैं, इसलिए हम एक सरणी का उपयोग यह चिह्नित करने के लिए करेंगे कि कोई नोड पहले ही आ चुका है या नहीं।
Input : The Adjacency matrix of the graph. A B C D E F A 0 1 1 1 0 0 B 1 0 0 1 1 0 C 1 0 0 1 0 1 D 1 1 1 0 1 1 E 0 1 0 1 0 1 F 0 0 1 1 1 0 Output : BFS Traversal: B A D E C F
एल्गोरिदम
bfs(कोने, प्रारंभ)
इनपुट − शीर्षों की सूची, और आरंभिक शीर्ष।
आउटपुट - अगर ग्राफ़ जुड़ा हुआ है, तो सभी नोड्स को ट्रैवर्स करें।
Begin define an empty queue que at first mark all nodes status as unvisited add the start vertex into the que while que is not empty, do delete item from que and set to u display the vertex u for all vertices 1 adjacent with u, do if vertices[i] is unvisited, then mark vertices[i] as temporarily visited add v into the queue mark done mark u as completely visited done End
उदाहरण
#include<iostream>
#include<queue>
#define NODE 6
using namespace std;
class node {
public:
int val;
int state; //status
};
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
};
void bfs(node *vert, node s) {
node u;
int i, j;
queue<node> que;
for(i = 0; i<NODE; i++) {
vert[i].state = 0; //not visited
}
vert[s.val].state = 1;//visited
que.push(s); //insert starting node
while(!que.empty()) {
u = que.front(); //delete from queue and print
que.pop();
cout << char(u.val+'A') << " ";
for(i = 0; i<NODE; i++) {
if(graph[i][u.val]) {
//when the node is non-visited
if(vert[i].state == 0) {
vert[i].state = 1;
que.push(vert[i]);
}
}
}
u.state = 2;//completed for node u
}
}
int main() {
node vertices[NODE];
node start;
char s;
for(int i = 0; i<NODE; i++) {
vertices[i].val = i;
}
s = 'B';//starting vertex B
start.val = s-'A';
cout << "BFS Traversal: ";
bfs(vertices, start);
cout << endl;
} आउटपुट
BFS Traversal: B A D E C F