ग्राफ़ के लिए चौड़ाई पहली खोज (बीएफएस)

ब्रेडथ फर्स्ट सर्च (बीएफएस) ट्रैवर्सल एक एल्गोरिथम है, जिसका उपयोग किसी दिए गए ग्राफ के सभी नोड्स पर जाने के लिए किया जाता है। इस ट्रैवर्सल एल्गोरिथम में एक नोड का चयन किया जाता है और फिर सभी आसन्न नोड्स को एक-एक करके देखा जाता है। आसन्न सभी शीर्षों को पूरा करने के बाद, यह एक और शीर्ष की जाँच करने के लिए आगे बढ़ता है और अपने आसन्न शीर्षों की फिर से जाँच करता है।

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

ग्राफ़ में कभी-कभी, हमें कुछ चक्र मिल सकते हैं, इसलिए हम एक सरणी का उपयोग यह चिह्नित करने के लिए करेंगे कि कोई नोड पहले ही आ चुका है या नहीं।

इनपुट और आउटपुट

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(vertices, start)

इनपुट - शीर्षों की सूची, और प्रारंभ शीर्ष।

आउटपुट - यदि ग्राफ़ जुड़ा हुआ है, तो सभी नोड्स को ट्रैवर्स करें।

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