一、先認識圖：頂點和邊的關係¶
在數據結構中，圖是由“頂點（Vertex）”和“邊（Edge）”組成的結構。比如我們熟悉的社交網絡：每個用戶是一個頂點，用戶之間的“好友關係”就是邊。再比如城市交通圖：每個城市是頂點，城市間的“道路”就是邊。
二、鄰接矩陣：最直觀的存儲方式¶
鄰接矩陣是圖最基礎的存儲方式，它用一個二維數組表示圖。數組的行和列對應圖的頂點，數組中的值（0或1）表示兩個頂點之間是否有邊（1表示有邊，0表示無）。
舉個例子：
假設有3個頂點（0、1、2），邊有：0-1、1-2。
鄰接矩陣可以表示爲：
0 1 2
0 0 1 0
1 1 0 1
2 0 1 0
- 第i行第j列的值
matrix[i][j]表示頂點i和頂點j之間是否有邊。 - 比如
matrix[0][1] = 1，說明頂點0和1之間有邊；matrix[2][1] = 1，說明頂點2和1之間有邊。
三、鄰接表：“鄰居鏈表”式的存儲¶
鄰接表是另一種更靈活的存儲方式，它爲每個頂點單獨維護一個鏈表（或動態數組），用來存儲與該頂點直接相連的所有“鄰居”。
同樣以上面的例子：
頂點0的鄰居是1，所以鄰接表爲 0: [1]；
頂點1的鄰居是0和2，所以鄰接表爲 1: [0, 2]；
頂點2的鄰居是1，所以鄰接表爲 2: [1]。
簡單說：每個頂點後面跟着它的“鄰居列表”，沒有鄰居的頂點（孤立頂點）鄰接表爲空。
四、對比：鄰接矩陣 vs 鄰接表¶
| 維度 | 鄰接矩陣 | 鄰接表 |
|---|---|---|
| 空間佔用 | 需 n² 空間（n爲頂點數），無論邊多少都佔滿n²個位置。 |
僅佔 n + e 空間（e爲邊數），只存實際存在的邊。 |
| 查找邊 | 直接查二維數組，時間 O(1)（比如查頂點i和j是否有邊，看 matrix[i][j]）。 |
需遍歷頂點i的鄰接表，時間 O(degree(i))（degree(i)是頂點i的鄰居數）。 |
| 遍歷鄰居 | 需遍歷整個一行（比如頂點i的鄰接行），時間 O(n)（不管有沒有邊，都要檢查n個位置）。 |
只需遍歷鄰接表，時間 O(degree(i))（只訪問實際存在的邊）。 |
五、鄰接表爲什麼更好？¶
核心優勢：針對“稀疏圖”的高效性
在實際問題中，大多數圖是稀疏圖（比如社交網絡中，每個人的好友數遠少於總人數）。此時：
- 鄰接矩陣 會浪費大量空間（比如1000個頂點的圖，若只有1000條邊，鄰接矩陣仍需1000×1000=100萬空間，而鄰接表只需1000+1000=2000空間）。
- 鄰接表 只存實際邊，空間效率更高；遍歷鄰居時，也只訪問存在的邊，時間效率更高。
例外情況：如果是稠密圖（比如完全圖，每個頂點都和其他所有頂點相連），鄰接矩陣可能更合適（但這種情況較少見）。
六、總結¶
鄰接表是稀疏圖的“高效存儲神器”，它通過“鄰居鏈表”的方式，用更少的空間存儲實際邊，並更快地遍歷頂點的鄰居。相比之下，鄰接矩陣雖然直觀，但在大多數實際場景中（尤其是稀疏圖），鄰接表是更優選擇。
在編程中，鄰接表是處理圖問題（如最短路徑、拓撲排序）的主流存儲方式，也是初學者需要掌握的核心數據結構之一。
簡單一句話記住：鄰接表是“只存朋友的列表”，比鄰接矩陣這個“存所有人的表格”更省空間、更快！