जावास्क्रिप्ट में ब्रेड्थ-फर्स्ट सर्च ट्रैवर्सल

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

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

आइए देखते हैं कि BFS ट्रैवर्सल कैसे काम करता है इसका एक चित्रण:

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

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

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

उदाहरण

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

आप इस फ़ंक्शन का परीक्षण इस तरह कर सकते हैं:

उदाहरण

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
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");

आउटपुट

इससे निम्न आउटपुट मिलेगा:

A C B D G E F