簡單說，就是有多個節點(vertex)，且彼此有些連接線(edge)的資料結構，以下都是 graph :

並且 graph 種類還能分為有向 & 無向兩種 :

• 無方向性圖（Undirected Graph): 圖的邊線沒有標示方向的箭頭，邊線只代表節點間是相連的
• 方向性圖（Directed Graph：在節點和節點間的邊線加上箭號，表示單向性

應用範例

Graph 的應用還蠻多的，例如 :

1. 社交網路
2. 地點定位/地圖
3. 視覺化階層式的資料
4. 一些推薦項目(ex: 你可能也喜歡...

Graph 的表示方式

以下介紹兩種常見 Graph 的表示方式 :

1. Adjacency matrix

用一個二維陣列表示，例如以下圖片是無向的 graph，1、2 兩個節點之間有 edge，所以 [1][2] 和 [2][1] 都是 1。

如果是有向的圖，陣列不會是對稱的數字，也就是說 [1][2] 是 1，但 [2][1] 不一定是 1。

2. Adjacency List

會先以一個一維陣列列出所有的節點，再以 Linked list 表示所有與該節點相連的節點。例如節點 1 相連的節點有 2、3、4。

兩種方式的時間複雜度

資料表示範例

圖形走訪(Graph Traversal)

圖形的走訪主要分成兩種-BFS(廣度優先搜尋) & DFS(深度優先搜尋)，Tree 和 Graph 都可以執行這兩個演算法。

Breadth-First Search(BFS，廣度優先搜尋)

從特定節點開始找，假設該特定節點有 3 個鄰居節點，那就會一一將 3 個鄰居節點都找過，接著才往其中一個鄰居節點的其他節點查找。

演算法思路

要思考的幾個點如下:

1. BFS 的函式會接收一個參數當作起始節點
2. 用一個 queue 代表待走訪的節點
3. 用一個 result 陣列儲存走訪的結果，最後 BFS 函式會回傳此陣列
4. 用一個 visited 物件儲存訪問過的節點，因為 graph 有很多節點彼此相通的情況，例如 A 連到 B，B 連 C，C 也連 A，所以用 visited 物件去避免重複走訪
5. adjacencyList 代表的是記錄各節點的鄰居節點
6. 用 while 迴圈去做走訪

接著將上面的想法轉換成程式碼就如下，不過只是有關於 BFS 的片段的程式碼，包含整個 Graph 和相關操作函式的完整程式碼可以參考 javascript-data-structure/Graph。

breadthFirst(start) {
  const queue = [start];
  const result = [];
  const visited = {};
  let currentVertex;
  visited[start] = true;

  while (queue.length) {
    currentVertex = queue.shift();
    result.push(currentVertex);

    this.adjacencyList[currentVertex].forEach((neighbor) => {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    });
  }
  return result;
}

此演算法時間複雜度為 O(v + e)，v 是節點數量，e 是邊的數量。

Depth-First Search(DFS，深度優先搜尋)

從特定節點開始找，假設該特定節點有 3 個鄰居節點，那不會 3 個鄰居節點都找過，而是選擇其中一個鄰居節點查找後，再從該鄰居節點繼續往其鄰居節點查找。

演算法思路

可以有兩種做法，一種有用遞迴一種沒有，這裡使用遞迴的方式來作示範。

要思考的幾個點如下:

1. DFS 的函式會接收一個參數當作起始節點
2. 用一個 result 陣列儲存走訪的結果，最後 DFS 函式會回傳此陣列
3. 用一個 visited 物件儲存訪問過的節點
4. adjacencyList 代表的是記錄各節點的鄰居節點
5. 建立一個遞迴的函式，傳入當前走訪的節點當參數，如果已經走訪到盡頭就不繼續遞迴，反之則將當前走訪的節點標記走訪過，然後查找其鄰居節點繼續作遞迴。

adjacencyList 就像下圖左邊的物件，記錄著各節點的鄰居節點，而右邊的物件代表走訪過的節點，走過就紀錄 true。

接著將上面的想法轉換成程式碼就如下:

depthFirstRecursive(start) {
  const result = [];
  const visited = {};
  const adjacencyList = this.adjacencyList;

  (function dfs(vertex) {
    if (!vertex) return null;
    visited[vertex] = true;
    result.push(vertex);
    adjacencyList[vertex].forEach((neighbor) => {
      if (!visited[neighbor]) {
        return dfs(neighbor);
      }
    });
  })(start);

  return result;
}

Graph 的 BFS 和 DFS 比較

BFS

• 常搭配 queue 實作
• 在 Graph 中適合找最短路徑，如果是 DFS 要跑完所有路徑才能求出最短路徑
• 消耗較多記憶體

DFS

• 常搭配 stack 實作
• 在 Graph 中找某點是否存在較適合

圖形走訪的常見應用

1. web 爬蟲(BFS)
2. P2P Networks
3. 找到最相近的搜尋結果/推薦，例如臉書的好友網路圖，透過重疊的數量比重去做推薦
4. 最短路徑問題

參考資料

Graph: Intro(簡介)