Breadth-First Search Traversal ใน JavaScript

BFS เยี่ยม neighbor vertices ก่อน child vertices และใช้ queue ในการค้นหา การทำงานของ BFS:

• Visit adjacent unvisited vertex Mark visited Display Insert ลง queue
• ถ้าไม่มี adjacent vertex remove first vertex จาก queue
• ทำซ้ำ Rule 1 และ 2 จน queue ว่าง

มาดูภาพประกอบ BFS Traversal:

Step	Traversal	Description
1		Initialize the queue.
2		เริ่ม visit S (starting node) mark visited
3		เห็น unvisited adjacent จาก S มี 3 nodes แต่ alphabetical เลือก A mark visited enqueue
4		Unvisited adjacent จาก S ต่อคือ B mark visited enqueue
5		Unvisited adjacent จาก S ต่อคือ C mark visited enqueue
6		S ไม่มี unvisited adjacent nodes Dequeue พบ A
7		จาก A มี D เป็น unvisited adjacent mark visited enqueue

ในขั้นนี้ไม่มี unmarked nodes แล้ว แต่ตามอัลกอริทึมเรา dequeue ต่อจน queue ว่าง โปรแกรมจบ

มาดูการนำไปใช้ใน JavaScript:

ตัวอย่างโค้ด

BFS(node) {
  // สร้าง Queue ใส่ initial node
  let q = new Queue(this.nodes.length);
  let explored = new Set();
  q.enqueue(node);
  // Mark first node explored
  explored.add(node);
  // ดำเนินต่อจน queue ว่าง
  while (!q.isEmpty()) {
    let t = q.dequeue();
    // Log ทุก element ที่ออกจาก Queue
    console.log(t);
    // 1. ใน edges object หา nodes ที่เชื่อมโดยตรง
    // 2. Filter nodes ที่ explored แล้ว
    // 3. Mark unexplored nodes explored และเพิ่มลง 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