चौड़ाई पहली खोज (बीएफएस) ट्रैवर्सल एक एल्गोरिथम है, जिसका उपयोग किसी दिए गए ग्राफ़ के सभी नोड्स पर जाने के लिए किया जाता है। इस ट्रैवर्सल एल्गोरिथम में एक नोड का चयन किया जाता है और फिर सभी आसन्न नोड्स को एक-एक करके देखा जाता है। आसन्न सभी शीर्षों को पूरा करने के बाद, यह एक और शीर्षों की जाँच करने के लिए आगे बढ़ता है और अपने आसन्न शीर्षों को फिर से जाँचता है।
इस एल्गोरिथ्म को लागू करने के लिए, हमें कतार डेटा संरचना का उपयोग करने की आवश्यकता है। सभी आसन्न कोने कतार में जोड़ दिए जाते हैं, जब सभी आसन्न कोने पूरे हो जाते हैं, तो एक आइटम को कतार से हटा दिया जाता है और फिर से उस शीर्ष से ट्रैवर्स करना शुरू कर देता है।
ग्राफ़ में कभी-कभी, हमें कुछ चक्र मिल सकते हैं, इसलिए हम एक सरणी का उपयोग यह चिह्नित करने के लिए करेंगे कि कोई नोड पहले से ही आया है या नहीं।
इनपुट - ग्राफ का एडजेंसी मैट्रिक्स।
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
आउटपुट - बीएफएस ट्रैवर्सल:बी ए डी ई सी एफ
एल्गोरिदम
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;
typedef struct node{
int val;
int state; //status
}node;
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