打開社群軟體，你會看到好友名單；點進朋友的頁面，又能看到他的朋友。有些朋友彼此認識，有些人你追蹤了他、他卻沒有追蹤你。如果要用資料結構把這些人和人之間的關係存起來，該怎麼辦？

前幾天的樹可以處理階層關係，例如家族系譜或資料夾：每個節點最多只有一個父節點，從根節點一路往下分支，不會繞回來。但社群網路不是這樣：A 和 B、C 都是朋友，B 和 C 也互相認識，三個人繞成一圈，誰也不是誰的「上一層」。這種「任何人都可以和任何人連在一起」的關係，就要用圖形（graph）來表示。

圖形的用途很廣：地圖上的車站與路線、網頁之間的超連結、社群網路裡的人際關係，都可以畫成圖。今天先不急著寫處理圖的程式，而是把基本概念弄清楚：圖的定義、有向與無向、常見名詞，以及邊最多能有幾條；最後再回頭看，我們學過的樹其實是圖的一種特例。後面談圖的存放方式，以及走訪（依序拜訪圖中每個頂點的方法）時，都會用到今天的名詞。

圖由頂點和邊組成

圖（graph）由兩個集合組成，寫成 G = (V, E)：

• V 是頂點（vertex）的集合，每個頂點代表一個對象，例如社群網路中的一個人、地圖上的一個車站。
• E 是邊（edge）的集合，每條邊連接兩個頂點，代表這兩個對象之間有關係。

樹裡的點我們叫節點（node），圖裡的點通常叫頂點。

和樹相比，圖一般不指定根節點，也沒有父子之分，邊怎麼連都可以：可以繞成圈，也可以有頂點完全沒連到其他頂點。為了讓後面的公式單純，只討論兩種限制：邊的兩端不能是同一個頂點（自己連自己的邊稱為自環），兩個頂點之間也不能有重複的邊。

邊有方向嗎：無向圖與有向圖

依照邊有沒有方向，圖分成兩種：

• 無向圖（undirected graph）：邊沒有方向。連接頂點 u 和 v 的邊寫成 (u, v)，而 (u, v) 和 (v, u) 是同一條邊。例如「好友關係」：A 是 B 的好友，B 一定也是 A 的好友。
• 有向圖（directed graph）：邊有方向。從 u 指向 v 的邊寫成〈u, v〉，u 是起點，v 是終點，〈u, v〉和〈v, u〉是不同的邊。例如「追蹤」：A 追蹤 B，B 不一定追蹤 A。

兩張圖都用 A、B、C、D 四個頂點，各有 4 條邊。左邊是無向圖，線沒有方向。右邊是有向圖：A 指向 B，B 指向 C，C 指向 A，三個人繞成一圈，C 另外還指向 D。注意〈C, D〉只有一個方向：C 指向 D，但 D 沒有指向任何人。

認識常見名詞

圖的名詞比樹多一些，我們先用一張無向圖把它們認識一遍。這張圖有 6 個頂點、5 條邊，而且分成兩塊：

路徑和環用圖來看會更清楚。下圖用 A、B、C、D 四個頂點，把一條簡單路徑和一個環分別標出來：

無向圖的環至少要有三個不同的頂點。A → B → A 只是沿著同一條邊走去又走回來，同一條邊用了兩次，不符合「邊不重複」，所以不算環。有向圖的路徑要順著箭頭走，所以前一節右邊那張有向圖中，A → B → C → A 是一個環；D 沒有指出去的邊，不可能出現在任何環裡。

有向圖的「連通」要求也比較嚴格。由於路徑要順著方向走，有向圖中任意兩個頂點 u 和 v，必須既能從 u 走到 v，也能從 v 走到 u，才稱為強連通（strongly connected）。前一節右邊那張有向圖的 D 只進不出，走不到其他頂點，所以不是強連通。

這裡有個容易混淆的地方：Day 13 介紹過樹的「分支度」，指的是一個節點有幾個子節點，只算往下的邊。圖沒有上下之分，度數是所有連到這個頂點的邊，不管對方是誰。

邊最多有幾條

接下來看一個計數問題。假設圖有 n 個頂點、e 條邊，而且不含自環與重複邊，e 最多能是多少？

• 無向圖：每個頂點最多能和其他 n − 1 個頂點相連，n 個頂點合計 n(n − 1) 個連接。但每條邊被它的兩個端點各數了一次，所以要除以 2，最多是 n(n − 1) / 2 條邊。
• 有向圖：〈u, v〉和〈v, u〉是不同的邊，每個頂點最多有 n − 1 條指出去的邊，n 個頂點最多是 n(n − 1) 條邊。

邊數達到上限、任意兩個頂點之間都有邊的圖，稱為完全圖（complete graph）。下圖是 3、4、5 個頂點的無向完全圖：

代入公式，不同頂點數的邊數上限如下：

邊數上限大約和 n² 同一個量級：頂點數變成兩倍，上限大約變成四倍。不過現實中的圖通常遠遠沒有這麼多邊，例如一個人的好友數，通常比所有使用者的人數少很多。邊數遠少於上限的圖稱為稀疏圖（sparse graph），接近上限的稱為稠密圖（dense graph），兩者沒有嚴格的分界線。這個差別會影響下一篇要談的圖的存放方式。

度數總和等於邊數的兩倍

無向圖還有一個好用的關係：所有頂點的度數加起來，剛好是邊數的兩倍。原因很直接：每條邊有兩個端點，這條邊會讓兩端的頂點各增加 1 度，所以每條邊恰好貢獻 2 個度數。

用前面有 6 個頂點的那張圖驗算：A、B、C、D、E、F 的度數是 2、2、3、1、1、1，加起來是 10；邊有 5 條，2 × 5 = 10，兩邊相等。

這個關係可以拿來檢查有沒有數錯：度數總和一定是偶數。也就是說，度數是奇數的頂點，個數一定是偶數；前面那張圖中，度數為奇數的 C、D、E、F 剛好有 4 個。

有向圖也有對應的關係：每條邊有一個起點、一個終點，所以所有頂點的入度加起來等於邊數，出度加起來也等於邊數。前面的有向圖中，入度是 1、1、1、1，出度是 1、1、2、0，兩邊加起來都是 4，等於邊數。

樹是圖的特例

回頭看看我們學過的樹。從圖的角度來看，樹是連通而且沒有環的無向圖。Day 13 的樹有指定根節點，不過在圖裡不一定要指定：選任何一個頂點當根，把其他頂點依照離根幾條邊，一層一層往下排，就會得到我們熟悉的樹的樣子。又因為沒有環，樹中任意兩個頂點之間，只會有一條簡單路徑。

樹的邊數也有固定的值。n 個頂點要連成一塊，至少需要幾條邊？一開始 n 個頂點互不相連，等於有 n 個連通元件；每加一條邊，最多讓連通元件少一個，要剩下一個，至少要 n − 1 條邊。樹正好用了最少的邊：可以想像從一個頂點出發，每次用一條邊接上一個全新的頂點，接 n − 1 次，n 個頂點就全部連起來了，過程中不會出現環。這時再多加任何一條邊，它的兩端本來就走得到彼此，這條路徑加上新邊，就繞成一個環。所以 n 個頂點的樹，恰好有 n − 1 條邊。這是直覺說明，不是嚴格的證明。

Day 13 提過的森林，是零棵或多棵互不相連的樹。從圖的角度來看，森林就是沒有環、但不一定連通的無向圖，每個連通元件各是一棵樹。

最後把樹和圖整理成表格：

所以樹能表示的關係，圖也都能表示；圖多出來的自由度，換來了表達更複雜關係的能力，但也讓存放與走訪變得更麻煩。

小結

圖由頂點和邊組成，可以用來表示任意兩個對象之間的關係。邊有方向的是有向圖，沒有方向的是無向圖。理解度數、路徑、環、連通與連通元件這些名詞之後，就能描述一張圖的形狀；不含自環與重複邊時，n 個頂點的無向圖最多有 n(n − 1) / 2 條邊，並且所有頂點的度數總和永遠是邊數的兩倍。樹則是連通而且沒有環的無向圖，n 個頂點恰好有 n − 1 條邊。

今日重點：

• 圖 G = (V, E)：V 是頂點的集合，E 是邊的集合；本文不討論自環與重複邊。
• 無向圖的邊寫成 (u, v)，沒有方向；有向圖的邊寫成〈u, v〉，從 u 指向 v，〈u, v〉和〈v, u〉是不同的邊。
• 無向圖用度數描述頂點連了幾條邊；有向圖分成入度和出度。
• 路徑是依序經過的頂點，長度是邊數；簡單路徑的頂點不重複；環是起點和終點相同、邊不重複，其餘頂點也不重複的路徑。
• 無向圖中任兩個頂點都有路徑，就是連通圖；圖中不能再擴大的連通部分稱為連通元件。
• n 個頂點的無向圖最多 n(n − 1) / 2 條邊，有向圖最多 n(n − 1) 條邊；達到上限的稱為完全圖。
• 無向圖的度數總和等於邊數的兩倍；有向圖的入度總和、出度總和都等於邊數。
• 樹是連通而且沒有環的無向圖，n 個頂點恰好有 n − 1 條邊；森林是沒有環、但可以有多個連通元件的無向圖。

圖畫在紙上一目了然，但電腦只認得記憶體。下一篇要面對這個現實問題：是做一張「誰和誰有連線」的對照表，還是讓每個頂點各自帶一份朋友名單？這兩種做法，也就是鄰接矩陣（adjacency matrix）和鄰接串列（adjacency list），各有各的好處，我們下一篇來比一比。