Day 21 認識了圖的頂點、邊、度數和連通。圖畫在紙上一目了然，但電腦只認得記憶體：要怎麼讓程式「記住」誰和誰之間有邊？
今天介紹兩種常見的存法，一種是做一張「誰和誰有邊」的對照表，叫相鄰矩陣（adjacency matrix）；另一種是讓每個頂點各自帶一份朋友名單，叫相鄰串列（adjacency list）。兩種都用 Day 21 的同一張圖來說明。沒有特別註明時，圖都是無向圖，並沿用「不含自環與重複邊」的約定；n 代表頂點數，e 代表邊數。
相鄰矩陣是一個 n × n 的二維陣列（Day 6），頂點依序對應到各列與各欄。如果頂點 i 和頂點 j 之間有邊，第 i 列第 j 欄就記 1，沒有就記 0。圖不含自環，所以對角線（第 i 列第 i 欄）都是 0。
C 那一列是 1、1、0、1、0、0，表示 C 和 A、B、D 相鄰。無向圖的邊沒有方向，邊 (A, B) 要在「A 列 B 欄」和「B 列 A 欄」各記一次，所以矩陣會沿著對角線對稱。
剛剛的無向圖中，頂點的度數就是它那一列的總和：C 那一列有三個 1，度數是 3。
但有向圖的邊有方向，邊〈u, v〉只記在 u 列 v 欄這一格，所以矩陣不一定對稱。這時列總和是出度，欄總和是入度。下圖左邊是 Day 21 的有向圖，邊是〈A, B〉、〈B, C〉、〈C, A〉、〈C, D〉；右邊是它的相鄰矩陣，右側標出各列的總和（出度），下方標出各欄的總和（入度）：
以 C 為例：C 那一列總和是 2（指向 A 和 D），出度是 2；C 那一欄總和是 1（B 指向 C），入度是 1。
無向圖的每條邊占兩格，所以把全部格子加起來再除以 2，就是邊數：上面那張圖的總和是 10，e = 5。有向圖的每條邊只占一格，總和就是邊數。不管哪一種，都得把整張表掃過一遍，時間是 O(n²)。
要判斷整張圖是不是連通圖，也一樣費時。做法是從某個頂點出發，看看能不能走到所有頂點；每到一個頂點，就得掃它那一列的 n 個格子，才找得到它的相鄰頂點，n 個頂點合計是 O(n²)。怎麼「走」是下一篇圖的追蹤要講的，這裡先記住結論：用相鄰矩陣，求總邊數和判斷是否連通都要花 O(n²)。
相鄰串列的做法是：n 個頂點，各準備一條鏈結串列（Day 7），串列裡放的是和這個頂點相鄰的頂點。每條串列用一個串列頭指標指向第一個節點，後文簡稱為串列頭。n 個串列頭放在一個陣列裡，用頂點的編號就能直接找到它的串列。如果頂點是孤立的、沒有任何相鄰頂點，它的串列頭就直接指向 NULL。
串列裡的每個節點，記著相鄰頂點的編號，以及指向下一個節點的連結。
圖中 C 的串列是 A → B → D，表示 C 和這三個頂點相鄰。串列裡相鄰頂點的排列順序不影響圖本身，這裡一律由小排到大。
無向圖的每條邊會出現兩次：邊 (A, B) 讓 B 出現在 A 的串列裡，同時也讓 A 出現在 B 的串列裡。所以全部的串列節點共有 10 個，剛好是 2 × 邊數，這就是 Day 21 的「度數總和 = 2 × 邊數」。
無向圖中，頂點的度數就是它那條串列的節點個數：C 的串列有 3 個節點，度數是 3。只需要走完自己的串列，不必像矩陣一樣掃過 n 個格子。
有向圖的邊〈u, v〉只會放進 u 的串列裡，所以串列的長度就是出度；入度則要把所有串列掃過一遍，數該頂點出現幾次，時間是 O(n + e)。
求總邊數時，把所有串列的節點數加起來（無向圖再除以 2）。這要走過 n 個串列頭和全部的節點，時間是 O(n + e)。判斷是否連通時，也只需要順著串列走到相鄰的頂點，不必檢查 0，時間同樣是 O(n + e)，下一篇會看到做法。
相鄰矩陣用 n × n 的表格記錄誰和誰有邊，查一條邊很快，度數是列（欄）總和；但求總邊數和判斷是否連通，都得掃過整張表，要 O(n²)，邊少的時候大多浪費在 0 上。相鄰串列為每個頂點準備一條串列，只記真正存在的邊，空間是 O(n + e)，度數就是串列長度，求總邊數和判斷是否連通可以降到 O(n + e)。
今日重點：
圖存好了，下一篇會看如何在圖逛一圈，這就是圖的追蹤。從一個人出發，是先把他所有的朋友都拜訪一遍、再往外擴一圈，還是挑一位朋友一路追到底，走不下去再退回來？前者會用到 Day 11 的佇列，後者則是 Day 10 的堆疊。
iThome鐵人賽
看影片追技術