跳至主要内容

Graph

Graph（中文通常翻譯為「圖」）是一種用來表示「物體」與「物體之間關係」的資料結構

這裡的「圖」不是指照片或圖片，而是一個像「網路」一樣的網狀結構。例如臉書上的好友關係、Google 地圖上的道路，都可以用 Graph 來表示。

Graph

組成要素​

  • 頂點 (Vertex / Node)
    • 代表「物體」本身，例如一個人、一個城市或一個網頁
  • 邊 (Edge)
    • 代表點跟點之間的「關係」，也就是連接兩個頂點的線
    • 例如兩個人是朋友、兩個城市之間有道路

常見種類​

根據關係的不同，Graph 可以分成以下幾種：

  1. 無向圖 (Undirected Graph)：線沒有方向，關係是雙向的。
    • 例子：臉書的好友關係。你對他是好友，他對你也就自然是好友。
  2. 有向圖 (Directed Graph)：線有箭頭，代表單向關係。
    • 例子：IG 的追蹤。你可以追蹤某個明星，但明星不一定會追蹤你。
  3. 權重圖 (Weighted Graph)：每條線上都有一個權重，可代表距離、成本或時間。
    • 例子：地圖導航。城市之間的連線會寫上「開車需要 30 分鐘」或「距離 15 公里」。

儲存 Graph 的方式​

電腦沒辦法直接看懂畫出來的圖，所以常用以下兩種方法把 Graph 存進記憶體裡：

  • Adjacency Matrix
  • Adjacency List

鄰接矩陣 (Adjacency Matrix)​

Adjacency Matrix - 圖源：演算法筆記

用一個二維的格子（表格）來記錄。

如果點 A 和點 B 有連線，就在格子交界處記為 1（或是寫上權重），沒連線就記為 0。

  • 優點：想要查「點 A 和點 B 有沒有連線」非常快。
  • 缺點：如果點很多、但線很少，會浪費很多格子空間存 0。

鄰接串列 (Adjacency List)​

Adjacency Lists - 圖源：演算法筆記

每一個頂點自己拿一張清單，只列出跟自己有連線的其他頂點。

  • 優點：非常省空間，有幾條線就用多少空間。
  • 缺點：想要查特定的兩點有沒有連線，必須要把清單從頭到尾遍歷過。

比較​

操作 / 空間Adjacency MatrixAdjacency List贏家
空間複雜度 (記憶體容量)O(V^2)O(V + E)Adjacency List (省空間)
加入新頂點 (Add Vertex)O(V^2)O(1)Adjacency List (速度快)
加入新邊 (Add Edge)O(1)O(1)平手
刪除頂點 (Remove Vertex)O(V^2)O(V + E)Adjacency List (速度快)
刪除邊 (Remove Edge)O(1)O(U)Adjacency Matrix (速度快)
查詢兩點是否有連線O(1)O(U)Adjacency Matrix (速度快)
  • V：頂點 (Vertex / Node) 的總數
  • E：邊 (Edge) 的總數
  • U：與該點相連的邊的數量，一個點可能跟所有點相連，所以最多是 Vertex 的總數 (V)
ADJACENCY LISTADJACENCY MATRIX
稀疏圖 (Sparse Graph)適合耗費空間
迭代 edges快慢
找特定 edge慢快

真實應用情境下 Sparse Graph 比較常見，所以多數情況會比較適合用 Adjacency List，在刷題時一般也都是用 Adjacency List。

實作​

Undirected Graph​

實作 Undirected 同時也是 Unweighted 的 Graph：

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (this.adjacencyList[vertex]) return; // 已經存在就不需要再次加入
    this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  removeEdge(v1, v2) {
    this.adjacencyList[v1] = this.adjacencyList[v1].filter(
      (vertex) => vertex !== v2
    );
    this.adjacencyList[v2] = this.adjacencyList[v2].filter(
      (vertex) => vertex !== v1
    );
  }

  removeVertex(vertex) {
    const list = this.adjacencyList[vertex];
    if (!list) return undefined;
    list.forEach((v2) => {
      this.removeEdge(vertex, v2);  // 每個和 vertex 相連的都斷開連結
    })
    delete this.adjacencyList[vertex];
  }
}

在解題的時候，比較常見的做法是只在 function sol 裡面定義 list 作為 Graph 的起點，利用物件導向另外定義物件比較費時。

遍歷 Graph 的演算法，寫在 Graph Traversal 裡，歡迎前去參考。

Weighted Graph​

和 Undirected Graph 差不多，只是在 edge 加上權重而已：

class WeightedGraph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2, weight) {
    this.adjacencyList[v1].push({ node: v2, weight });
    this.adjacencyList[v2].push({ node: v1, weight });
  }

  // 其他 method 皆相同
}

但 Weighted Graph 的重點會放在搜尋兩個點之間的最短路徑，也就是 Shortest Path Problem 上，較常見的做法是 Dijkstra's Algorithm。

最後於 更新