जावास्क्रिप्ट में चौड़ाई-प्रथम खोज ट्रैवर्सल

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

• आसन्न अगोचर शीर्ष पर जाएं। इसे विज़िट किए गए के रूप में चिह्नित करें। इसे प्रदर्शित करें। इसे एक कतार में डालें।
• यदि कोई आसन्न शीर्ष नहीं मिलता है, तो पहले शीर्ष को कतार से हटा दें।
• नियम 1 और नियम 2 को तब तक दोहराएं जब तक कि कतार खाली न हो जाए।

आइए एक उदाहरण देखें कि बीएफएस ट्रैवर्सल कैसे काम करता है:

कदम
1		कतार को प्रारंभ करें।
2		हम S . पर जाकर शुरुआत करते हैं (शुरुआती नोड) और इसे विज़िट किए गए के रूप में चिह्नित करें।
3		फिर हम S. . से एक असंबद्ध आसन्न नोड देखते हैं इस उदाहरण में, हमारे पास तीन नोड हैं लेकिन वर्णानुक्रम में हम A, . चुनते हैं इसे विज़िट के रूप में चिह्नित करें और इसे एनक्यू करें।
4		अगला, S . से अगम्य आसन्न नोड है बी . हम इसे विज़िट किए गए के रूप में चिह्नित करते हैं और इसे संलग्न करते हैं।
5		अगला, S . से अगम्य आसन्न नोड है सी . हम इसे विज़िट किए गए के रूप में चिह्नित करते हैं और इसे संलग्न करते हैं।
6		अब, एस बिना विज़िट किए गए आसन्न नोड्स के साथ नहीं छोड़ा गया है। इसलिए, हम हटाते हैं और पाते हैं A ।
7		से A हमारे पास D . है एक अनजान आसन्न नोड के रूप में। हम इसे विज़िट किए गए के रूप में चिह्नित करते हैं और इसे संलग्न करते हैं।

इस स्तर पर, हमारे पास कोई अचिह्नित (अनदेखा) नोड नहीं बचा है। लेकिन एल्गोरिथम के अनुसार हम सभी अनविजिटेड नोड्स प्राप्त करने के लिए डीक्यूइंग करते रहते हैं। जब कतार खाली हो जाती है, तो कार्यक्रम समाप्त हो जाता है।

आइए देखें कि हम इसे जावास्क्रिप्ट में कैसे लागू कर सकते हैं।

उदाहरण

BFS(node) {// एक कतार बनाएं और उसमें अपना प्रारंभिक नोड जोड़ें q =new Queue(this.nodes.length); चलो पता लगाया =नया सेट (); क्यू.एनक्यू (नोड); // पहले नोड को एक्सप्लोर किए गए के रूप में चिह्नित करें। जोड़ें (नोड); // हम तब तक जारी रखेंगे जब तक कि हमारी कतार खाली न हो जाए (!q.isEmpty()) {let t =q.dequeue(); // कतार कंसोल से बाहर आने वाले प्रत्येक तत्व को लॉग करें। लॉग (टी); // 1. किनारों की वस्तु में, हम उन नोड्स की खोज करते हैं जिनसे यह नोड सीधे जुड़ा हुआ है। // 2. हम उन नोड्स को फ़िल्टर करते हैं जिन्हें पहले ही खोजा जा चुका है। // 3. फिर हम प्रत्येक बेरोज़गार नोड को एक्सप्लोर के रूप में चिह्नित करते हैं और इसे कतार में जोड़ते हैं। this.edges[t] .filter(n => !explored.has(n)) .forEach(n => {explored.add(n); q.enqueue(n); }); }} 

 आप -
 . का उपयोग करके इस फ़ंक्शन का परीक्षण कर सकते हैं 
उदाहरण
 
चलो g =नया ग्राफ़ ();g.addNode("A");g.addNode("B");g.addNode("C");g.addNode("D");g.addNode ("ई");g.addNode("F");g.addNode("G");g.addEdge("A", "C");g.addEdge("A", "B"); g.addEdge("A", "D");g.addEdge("D", "E");g.addEdge("E", "F");g.addEdge("B", "G" );g.BFS("A");
 
आउटपुट
 

 यह आउटपुट देगा -
 
एसीबीडीजीईएफ