การข้ามผ่านการค้นหาแบบกว้างก่อนใน Javascript

BFS เยี่ยมชมจุดยอดเพื่อนบ้านก่อนที่จะไปที่จุดยอดย่อย และใช้คิวในกระบวนการค้นหา ต่อไปนี้เป็นวิธีการทำงานของ BFS -

• เยี่ยมชมจุดยอดที่ไม่ได้เยี่ยมชมที่อยู่ติดกัน ทำเครื่องหมายว่าเยี่ยมชมแล้ว แสดงมัน ใส่ในคิว
• หากไม่พบจุดยอดที่อยู่ติดกัน ให้นำจุดยอดแรกออกจากคิว
• ทำซ้ำกฎ 1 และกฎ 2 จนกว่าคิวจะว่าง

ให้เราดูภาพประกอบว่า BFS Traversal ทำงานอย่างไร:

ขั้นตอน	ข้ามผ่าน	คำอธิบาย
1		เริ่มต้นคิว
2		เราเริ่มต้นด้วยการไปที่ S (โหนดเริ่มต้น) และทำเครื่องหมายว่าเข้าชมแล้ว
3		จากนั้นเราจะเห็นโหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชมจาก S. ในตัวอย่างนี้ เรามีสามโหนด แต่ตามลำดับตัวอักษร เราเลือก A, ทำเครื่องหมายว่าเข้าชมแล้วเข้าคิว
4		ถัดไป โหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชมจาก S คือข . เราทำเครื่องหมายว่าเข้าชมแล้วและจัดคิวให้
5		ถัดไป โหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชมจาก S คือ C . เราทำเครื่องหมายว่าเข้าชมแล้วและจัดคิวให้
6		เอาล่ะ ซ ถูกทิ้งไว้โดยไม่มีโหนดที่อยู่ติดกันที่ยังไม่ได้เยี่ยมชม เลยดับเครื่องและพบว่า A .
7		ตั้งแต่ A เรามี D เป็นโหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชม เราทำเครื่องหมายว่าเข้าชมแล้วและจัดคิวให้

ในขั้นตอนนี้ เราจะไม่มีโหนดที่ไม่ได้ทำเครื่องหมาย (ไม่ได้เยี่ยมชม) แต่ตามอัลกอริธึม เราจะทำการ dequeuing ต่อไป เพื่อให้ได้โหนดที่ยังไม่ได้เยี่ยมชมทั้งหมด เมื่อคิวว่าง โปรแกรมก็จบ

มาดูกันว่าเราจะใช้สิ่งนี้ใน JavaScript ได้อย่างไร

ตัวอย่าง

BFS(node) {
   // Create a Queue and add our initial node in it
   let q = new Queue(this.nodes.length);
   let explored = new Set();
   q.enqueue(node);

   // Mark the first node as explored explored.
   add(node);

   // We'll continue till our queue gets empty
   while (!q.isEmpty()) {
      let t = q.dequeue();

      // Log every element that comes out of the Queue
      console.log(t);

      // 1. In the edges object, we search for nodes this node is directly connected to.
      // 2. We filter out the nodes that have already been explored.
      // 3. Then we mark each unexplored node as explored and add it to the queue.
      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