終於來到新單元啦！前面一路從 Bubble Sort、Quick Sort 學到遞迴，今天要開始認識一個新的資料結構：Graph（圖）。

Graph 對我來說其實有一種莫名的親切感，因為平常使用 VS Code 時就常常看到 Git Graph。但仔細想想，我好像一直知道這個名字，卻從來沒有認真想過：

Graph 到底是什麼？

Graph 是什麼？

查資料時看到一個很好理解的說法：

「『圖』是一種用來記錄關聯、關係的東西。」

這句話引用自演算法筆記－Graph。

這裡的「圖」不是圖片，而是一種用來描述資料彼此之間關係的資料結構。

以前接觸 Array 時，資料通常是一個接著一個：

A → B → C → D

但現實中的資料不一定這麼單純。

例如地圖上的一個地點可能同時連接好幾條道路；社群網站中的一個人，也可能同時跟很多人產生關係。

    B
   / \
  A   D
   \ /
    C

這種不是單純「上一個、下一個」，而是彼此形成網狀關係的資料，就很適合使用 Graph 來表示。

Graph 最基本的 Vertex 與 Edge

一張 Graph 最基本會由兩個東西組成：

• Vertex（頂點 / Node）：Graph 裡面的「點」。
• Edge（邊）：Vertex 之間的「連線」。

例如把地點畫成 Graph：

A ─── B
│     │
C ─── D

A、B、C、D 就是 Vertex，而中間的線就是 Edge，代表兩個地點之間可以互相到達。

那 Path 又是什麼？

假設今天我要從 A 走到 D，可以有：

A → B → D

也可以：

A → C → D

從一個 Vertex 出發，沿著 Edge 經過其他 Vertex，最後到達目的地，這一連串經過的路線就可以稱為 Path（路徑）。

所以 Edge 是「兩個點之間的連線」，Path 則可能是「由很多條 Edge 組成的一整條路線」，兩個概念其實不太一樣。

每條 Edge 還可以有 Weight

不過現實中的道路通常不會完全一樣。

A ──5── B
│       │
2       3
│       │
C ──4── D

Edge 上的數字可以代表 Weight（權重）。

Weight 不一定只能代表距離，也可以是時間、費用或其他成本。

所以一條 Edge 除了可以告訴我們「A 和 B 有關係」，還可以進一步記錄這段關係的成本。

至於當一張 Graph 有很多條不同的 Path，而且每條 Edge 又有不同的 Weight 時，這些數字可以拿來做什麼，就留到後面再繼續研究。

Graph 還有方向與連通性的差別

Edge 也不一定都是雙向的。

A → B

代表 A 可以走到 B，但 B 不一定能回到 A，這種就是 Directed Graph（有向圖）；如果兩邊都可以互相到達，則是 Undirected Graph（無向圖）。

另外還會看到 Connected（連通） 的概念。

A ─ B ─ C

D ─ E

A 可以走到 B、C，卻沒有任何 Path 可以走到 D、E，代表這張 Graph 並不是所有 Vertex 都連在一起。

今天小結

目前看下來，我覺得 Graph 最重要的概念就是：

Vertex 是「有哪些點」、Edge 是「點之間有什麼關係」、Path 是「可以怎麼走」，而 Weight 則讓每一條路有了不同的成本。

但程式又要怎麼知道 A 跟誰相連、B 又有哪些 Neighbor？

下一篇就來研究看看：Graph 要怎麼放進 JavaScript？

參考資料

演算法筆記，〈Graph〉
https://web.ntnu.edu.tw/~algo/Graph.html

Amber，〈資料結構－學習筆記（7）：Graph 圖〉
https://medium.com/@amber.fragments/資料結構-學習筆記-7-graph-圖-d4359fb6f19a

Hello Algo，〈圖〉
https://www.hello-algo.com/zh-hant/chapter_graph/graph/