Depth-First Search Traversal ใน JavaScript

DFS เยี่ยม child vertices ก่อน sibling vertices คือ traverse depth ของ path ใด path หนึ่งก่อนจะ explore breadth Stack (มักเป็น call stack ผ่าน recursion) มักใช้ในการ implement

การทำงานของ DFS:

• Visit adjacent unvisited vertex Mark visited Display Push ลง stack
• ถ้าไม่มี adjacent vertex pop vertex จาก stack (จะ pop ทุก vertices ที่ไม่มี adjacent vertices)
• ทำซ้ำ Rule 1 และ 2 จน stack ว่าง

มาดูภาพประกอบ DFS traversal:

Step	Traversal	Description
1		Initialize the stack.
2		Mark S visited ใส่ stack Explore unvisited adjacent node จาก S มี 3 nodes เลือกตาม alphabetical order
3		Mark A visited ใส่ stack Explore unvisited adjacent จาก A ทั้ง S และ D adjacent แต่สนใจ unvisited เท่านั้น
4		Visit D mark visited ใส่ stack มี B และ C adjacent กับ D ทั้งคู่ unvisited เลือก alphabetical order
5		เลือก B mark visited ใส่ stack B ไม่มี unvisited adjacent node Pop B ออกจาก stack
6		เช็ค stack top กลับไป node ก่อนหน้า เช็ค unvisited nodes พบ D บน stack top
7		Unvisited adjacent จาก D คือ C Visit C mark visited ใส่ stack

C ไม่มี unvisited adjacent nodes เรา pop stack จนเจอ node ที่มี unvisited adjacent ในกรณีนี้ไม่มี จน stack ว่าง มาดูการนำไปใช้ใน JavaScript:

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

DFS(node) {
  // สร้าง Stack ใส่ initial node
  let s = new Stack(this.nodes.length);
  let explored = new Set();
  s.push(node);
  // Mark first node explored
  explored.add(node);
  // ดำเนินต่อจน Stack ว่าง
  while (!s.isEmpty()) {
    let t = s.pop();
    // Log ทุก element ที่ออกจาก Stack
    console.log(t);
    // 1. ใน edges object หา nodes ที่เชื่อมโดยตรง
    // 2. Filter nodes ที่ explored แล้ว
    // 3. Mark unexplored nodes explored และ push ลง Stack
    this.edges[t]
      .filter(n => !explored.has(n))
      .forEach(n => {
        explored.add(n);
        s.push(n);
      });
  }
}

ง่ายมาก เราแค่เปลี่ยน queue เป็น stack ได้ DFS นี่คือความต่างเดียวระหว่าง BFS และ DFS DFS ยัง implement ด้วย recursion ได้ แต่หลีกเลี่ยงในกรณีนี้เพราะ graph ใหญ่ต้องการ memory เพิ่มสำหรับ call stack

ทดสอบได้ดังนี้:

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.DFS("A");

ผลลัพธ์

จะได้ผลลัพธ์:

A D E F B G C