---
tags: DSA in JavaScript
---
# ch. 27 Graph Traversal

圖的遍歷 (graph traversal)，就是探訪、更改或確認圖內的所有節點。

## 遍歷的應用

圖的廣泛應用也呈現在遍歷的過程中。

- P2P 網路連結
- 網路爬蟲
- 推薦系統 (影音、社群平台)
- 最短路徑問題 (shortest path problem)

## 遍歷的方法

就跟樹的遍歷一樣，有

- 深度優先搜尋
- 廣度優先搜尋

### 深度優先搜尋

深度優先會先以其中一條路線為主，直到發現該路線是死路，才開始探索其他路線
而這個有兩種實作方法：遞迴與迴圈

遞迴搜尋是使用 helper function 來實作

dfsRecursive (startVertex) {
  // 1. 建立一個用來存放已遍歷節點的物件
  const visited = {}
  const { adjacencyList } = this;
  // 2. 此處使用 IIFE 方式，簡化呼叫函式的步驟
  (function dfs (vertex) {
    // 2-1. 若參數不是節點 (ex: undefined)，回傳 null
    if (!vertex) return null
    // 2-2. 將代入的節點標記為已遍歷
    visited[vertex] = true
    // 2-3. 尋找該節點的所有鄰居節點
    adjacencyList[vertex].forEach(neighbor => {
    // 若其中一個鄰居節點未被遍歷，則再次呼叫 dfs 函式，並帶入那個尚未遍歷的節點
      if (!visited[neighbor]) return dfs(neighbor)
    })
  }(startVertex))
  
  // 3. 依照遍歷順序，回傳所有已遍歷的節點
  return Object.keys(visited)
}

迴圈搜尋與遞迴大同小異，不同之處在於使用堆疊結構與 while 迴圈

  dfsIterative (startVertex) {
    // 1. 建立空物件，用來存放已遍歷的節點
    const visited = {}
    const { adjacencyList } = this
    // 2. 建一個堆疊，存放之後會遍歷的節點，此處先放了 startVertex 做初始化
    const stack = [startVertex]
    // 3. 重複以下動作，直到堆疊被清空為止
    while (stack.length) {
      // 3-1. 從堆疊中拿出最後一個節點
      const vertex = stack.pop()
      // 3-2. 若該節點是未遍歷的節點...
      if (!visited[vertex]) {
        // 標記為已遍歷
        visited[vertex] = true
        // 將該節點的所有鄰居節點都送至堆疊內
        stack.push(...adjacencyList[vertex])
      }
    }
    
    // 4. 依照遍歷順序，回傳所有已遍歷的節點
    return Object.keys(visited)
  }

### 廣度優先搜尋

廣度優先則是先遍歷所有鄰居節點，再遍歷這些節點的鄰居節點。
會使用之前完成的 Queue 來實作遍歷的先後順序

bfs (startVertex) {
  // 1. 新增一個 queue 之後，將 startVertex 加進 queue 裡面
  const q = new Queue()
  q.enqueue(startVertex)
  // 2. 建一個存放已遍歷節點的物件，並標記 startVertex 已遍歷
  const visited = {}
  visited[startVertex] = true
  while (q.size) {
    // 3. 從 queue 裡面拿出一個節點
    const visit = q.dequeue()
    // 4. 開始處理 visit 節點的所有鄰居節點
    this.adjacencyList[visit].forEach(vertex => {
      // 5. 若有鄰居節點未遍歷，將它標記為已遍歷，並加入 queue
      if (!visited[vertex]) {
        visited[vertex] = true
        q.enqueue(vertex)
      }
    })
  }
  
  // 6. 依照遍歷順序，回傳所有節點
  return Object.keys(visited)
}