ग्राफ के लिए ब्रेडथ फर्स्ट सर्च (BFS)

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

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

ग्राफ में कभी-कभी, हमें कुछ साइकिल मिल सकते हैं, इसलिए हम एक ऐरे का उपयोग करेंगे जब कोई नोड पहले से विजिट किया गया हो या नहीं मार्क करने के लिए।

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

इनपुट: ग्राफ का एडजेसेंसी मैट्रिक्स। 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 ट्रैवर्सल: 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 i 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 #include #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 que; for(i = 0; i

आउटपुट
BFS Traversal: B A D E C F