Graph Traversal

如果你對於 Graph 還不熟，推薦先了解 Graph。

Graph Traversal 指的是 「把圖裡面所有的頂點都拜訪過一遍」 的過程。

因為圖（Graph）的結構非常自由，不像 Tree 有固定的上下階層（根節點），點跟點之間可能連成一個圈（環）。為了不重複造訪同個地方行程無窮迴圈，走訪時一定要有一個記錄，寫下哪些點已經去過（Visited），哪些點還沒去過。

Breadth First Search (BFS)

廣度優先如同 「地毯式搜索」。

從起點開始，先拜訪所有距離一步的鄰居，再拜訪距離兩步的鄰居，一圈一圈像水滴的漣漪一樣往外擴散。

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  
  ... // 其他 method

  bfs(start) {
    if (!this.adjacencyList[start]) return undefined;
    const result = [];
    const visited = new Set();
    const queue = [start];
    let node;
    while (queue.length) {
      node = queue.shift();
      if (visited.has(node)) continue; // 避免重複造訪
      result.push(node);
      visited.add(node);
      this.adjacencyList[node].forEach((neighbor) =>
        queue.push(neighbor)
      );
    }
    return result;
  }
}

Depth First Search (DFS)

選定一條路就一直往前走到底，直到遇到死巷子，才往回退一步（Backtrack），換另一條分支繼續走到底。

實作上又可分為迭代 (Iteration 使用 Stack) 或 遞迴 (Recursion) 兩種做法。

Iteration

建立一個 stack （使用 list/array）用來記錄即將要走訪的 vertex。

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  
  ... // 其他 method

  dfsIterative(start) {
    if (!this.adjacencyList[start]) return undefined;
    const result = [];
    const visited = new Set();
    const stack = [start];
    let node;
    while (stack.length) {
      node = stack.pop();
      if (visited.has(node) || !this.adjacencyList[node]?.length) {
        continue;
      }
      result.push(node);
      visited.add(node);
      this.adjacencyList[node].forEach((neighbor) =>
        stack.push(neighbor)
      );
    }
    return result;
  }
}

Recursion

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  
  ... // 其他 method

  dfsRecursive(start) {
    if (!this.adjacencyList[start]) return undefined;
    const result = [];
    const visited = new Set();
    const adjacencyList = this.adjacencyList;

    (function helper(node) {
      if (!node || !adjacencyList[node]?.length) return null;
      result.push(node);
      visited.add(node);
      adjacencyList[node].forEach(
        (neighbor) => !visited.has(node) && helper(neighbor)
      );
    })(start);

    return result;
  }
}

注意

其中要注意如果用 function 這個 keyword 建立 helper 的話，裡面是沒法取得 this.adjacencyList 的，因為此時的 this 是指 helper 本身。

所以要先設一個變數 adjacencyList，讓 helper 可以取得正確的 adjacencyList。如果用箭頭函式就不用另外建立變數。

複雜度比較

每個點（V）和每條邊（E）最多都被檢查一次。

演算法 / 實作方式	時間	空間	說明
BFS	O(V + E)	O(V)	Queue + 已拜訪集合 (Visited Set)
DFS (迭代 Iteration)	O(V + E)	O(V)	Stack + 已拜訪集合
DFS (遞迴 Recursion)	O(V + E)	O(V)	系統呼叫 Call Stack + 已拜訪集合