一張圖就是頂點，以及彼此相觸的那些對
你爬了好長一段路才到這裡：數迴圈、馴服遞迴關係式、權衡貪婪與動態規劃。現在，輸入的形狀變了。一張圖不過是一組 V 個頂點（點），外加一組 E 條邊（被連起來的點對）。一張公路圖、一個朋友網絡、一座迷宮、一張網頁之網、甚至這些指南本身的先修關係圖——只要你決定了什麼算一個點、什麼算一條連線，它們在那一刻就都成了圖。本階的全部重點，就是去探索這樣的結構：走訪它、搜尋它，並從走訪中讀出結構。但在圖以一種演算法能觸碰的形式住進記憶體之前，這一切都無從開始。
所以在我們跑出第一次搜尋之前，先面對一個更安靜的設計問題：我們該怎麼把圖寫下來？那個數學物件——「這些點、這些對」——並不告訴機器：當它問「頂點 5 的鄰居是誰？」時該往哪裡看。而這個查詢，正是本階每個演算法要做上百萬次的動作，所以邊的存法絕不是細節。它悄悄地替後面的一切定下執行時間。同一個演算法，可以快、也可以慢，差別只在於它的圖被怎麼打包。
兩個數字將主宰整段討論，現在就把它們釘住值得。V 是頂點數，E 是邊數。它們並不獨立：一張簡單圖最多大約只能有 V^2 / 2 條邊（每一對都連起來），所以 E 的範圍從 0 一路到 Theta(V^2)。當 E 逼近那個上限，我們說這張圖是稠密的；當 E 較接近 V——一張公路圖、一個每人只認識幾百人的社交圖——我們說它是稀疏的。你遇到的幾乎每張真實圖都是稀疏的，而光是這一個事實，就把整個存法決定給帶偏了，我們馬上就會看到。
矩陣：一張巨大的「有沒有」格子網
第一種表示法最直白。攤開一張 V 乘 V 的格子網，當頂點 i 到頂點 j 有一條邊時，就在格子 (i, j) 填上 1，沒有則填 0。這張格子網就是鄰接矩陣。它最大的魅力，在於它能瞬間回答的那個問題：「u 和 v 之間有沒有邊？」只是一次陣列查詢 A[u][v]，O(1) 時間——不必搜尋，讀一個格子就好。如果你的演算法一輩子都在戳特定的點對、問這兩個連著嗎，那矩陣就是一份大禮。
to: 0 1 2 3 # graph: 0-1, 0-2, 1-3 (undirected)
from 0 [ 0 1 1 0 ]
1 [ 1 0 0 1 ]
2 [ 1 0 0 0 ] # row 2 has a single 1 -> vertex 2 has 1 neighbour
3 [ 0 1 0 0 ] # undirected => the grid is symmetric across the diagonal但這張格子網收取一筆又陡又無條件的租金。它永遠佔用 Theta(V^2) 個格子，不管這張圖有一百萬條邊還是三條。一個十億人的社交網絡若這樣存，會需要十億平方個格子——一個不可能的 10^18——儘管幾乎每一格都是 0，因為大多數人彼此都是陌生人。更糟的是，我們實際上最常需要的那個動作——「列出 u 的鄰居好讓我去拜訪它們」——逼我們掃過 u 那一整列共 V 個格子，從 0 的汪洋裡篩出那寥寥幾個 1。為了找出也許只有兩三個鄰居，卻要花 O(V) 的工。
串列：每個頂點各自保有一本小通訊錄
第二種表示法拒絕儲存那些沉默。不用一張巨大的格子網，而是每個頂點各保一份短短的串列，只列出它真正的鄰居。頂點 0 的串列是 [1, 2]；頂點 2 的串列只有 [0]。這就是鄰接串列，它的哲學與矩陣恰好相反：它只把記憶體花在存在的邊上，從不花在不存在的邊上。總空間是 Theta(V + E)——每個頂點一格放它的串列開頭，加上每條邊一筆（無向圖則兩筆，因為每條邊都出現在兩端的通訊錄裡）。對一張 E 約等於 V 的稀疏圖，這在輸入規模上是線性的，而不是平方的。
現在交易翻轉了。列出 u 的鄰居——每次搜尋最家常的動作——只是走過 u 自己那份短串列，花的時間正比於 u 真實的鄰居數，而不是 V。把這個量在整趟走訪中加總起來，界就是那著名的 Theta(V + E)：每個頂點被碰一次、每條邊被走一次。正是這個乾淨的線性成本，說明了接下來兩篇指南裡的廣度優先與深度優先搜尋為何被描述成跑在 O(V + E)。它們直接從串列繼承了這個界；換成矩陣，同樣這些搜尋會慢到 O(V^2)，因為每一步「我的鄰居是誰？」都要付 O(V) 去掃一整列。
那串列放棄了什麼？矩陣的那記絕活。要在串列上問「u 和 v 之間有沒有邊？」，你得掃過 u 的鄰居串列去找 v——最壞情況是 O(u 的度數)，而不是 O(1)。對大多數圖搜尋來說，這個問題幾乎不會冒出來，這正是串列在實務上勝出的原因。但對一個圍繞著「在稠密圖上做常數時間邊查詢」打造的演算法，矩陣那瞬間查詢可能值得它那筆平方租金。沒有哪個結構單純地「比較好」；它們各自為不同的問題而調校。
誠實地選擇：取決於密度，也取決於你問什麼
把兩者並排，經驗法則幾乎自己就寫出來了。鄰接串列花 Theta(V + E) 空間，列出某頂點的鄰居所需時間正比於它的度數，回答「uv 是一條邊嗎？」是 O(度數)。鄰接矩陣花 Theta(V^2) 空間，列鄰居要 O(V)（你掃一整列），回答「uv 是一條邊嗎？」是 O(1)。對稀疏圖——壓倒性的常見情況，也是本階幾乎每篇指南所假設的——串列在空間與走訪速度兩方面都勝。對 E 本就已是 Theta(V^2) 的稠密圖，矩陣的空間不再浪費，而它 O(1) 的邊測試也成了一個真正的優勢。
對 Theta(V + E) 這個界「是什麼、不是什麼」要誠實，因為它很容易被過度解讀。它是漸進的，所以描述的是擴展趨勢，而非每個尺寸下的判決：對一張極小的圖，矩陣那塊扁平的陣列在真實硬體上可能贏過串列的指標追逐，因為連續的格子對快取友善，而那些隱藏常數偏袒較簡單的佈局。再者，V + E 確實是衡量一張圖輸入規模的正確尺度——兩個數，不是一個——所以一個只讀每個頂點與每條邊各一次的 O(V + E) 演算法，令人欣慰地，是最佳的：你不可能用比看一眼輸入還少的時間解掉一個問題。
表示法得一併扛起的變化
真實的圖有各種口味，而兩種表示法都能彎下身來配合。一張有向圖的邊是單行道（一個網頁連結、一道先修、一個推特追蹤）：在矩陣裡，A[u][v] = 1 不再逼著 A[v][u] = 1，於是格子網失去了沿對角線的對稱；在串列裡，邊 u -> v 只住在 u 的鄰居串列，絕不住在 v 的。一張無向圖把每條邊存在兩處，這就是為什麼無向鄰接串列裝有 2E 筆。一張加權圖替每條邊掛上一個數——一段距離、一筆成本、一個容量：矩陣只是把權重存進格子，而非光禿禿的 1；串列則存一個 (鄰居, 權重) 對，而非只存一個鄰居。
這些選擇不是記帳的瑣事；它們直接接線進後面的演算法。無向、無權的串列，正是下一篇指南用來建一棵 BFS 樹、去數以邊計的最短路徑、並測試一張圖能否乾淨地分成兩側的基底。有向串列，則是後面某篇指南所走過、用以產生一個拓樸排序或剝出連通分量的東西。加權圖則是最短路徑那一階所站立的地面。表示法是舞台；後面每個演算法都是一齣戲，只能在一座為承載它而搭的舞台上演出。