我們先想想，生活中有沒有這樣的場景：城市之間有公路連接，我們需要知道哪些城市之間可以通行；或者社交網絡裏，你和哪些人是朋友，朋友之間互相認識。這些都可以抽象成“圖”的概念。
一、圖的基本概念¶
在數據結構中，圖（Graph） 是由一組頂點（Vertex）和一組邊（Edge）組成的結構。頂點就是圖中的“點”，邊就是連接兩個頂點的“線”。
- 頂點（Vertex）：也叫“節點”，是圖的基本單元。比如社交網絡中的每個人就是一個頂點。
- 邊（Edge）：連接兩個頂點的關係，可能是單向或雙向的，可能有權重（比如公路的長度、航班的價格）。
圖的分類¶
圖有很多種類型，初學者需要了解最基礎的兩種：
1. 有向圖（Directed Graph）：邊是有方向的。例如，微博的關注關係（你關注某人，不代表對方關注你）。
2. 無向圖（Undirected Graph）：邊是無方向的。例如，微信好友關係（雙向）。
另外，還有有權圖和無權圖：
- 有權圖：邊帶有權重（數值），比如“城市A到城市B的距離是100公里”。
- 無權圖：邊沒有權重，只有連接關係（比如社交網絡的好友關係，只關心是否認識）。
二、鄰接表表示法：爲什麼需要它？¶
表示圖的方法有很多，最常見的是鄰接矩陣和鄰接表。鄰接矩陣是一個二維數組，用adj[i][j]表示頂點i和j之間是否有邊（1表示有，0表示無）。但鄰接矩陣有個缺點：當圖比較稀疏（邊數遠小於頂點數的平方）時，會浪費大量空間。例如，1000個頂點的圖，鄰接矩陣需要1000×1000=100萬個位置，而如果只有100條邊，大部分位置都是0。
鄰接表（Adjacency List） 是更高效的表示方法：它只存儲實際存在的邊，空間效率更高。核心思想是：每個頂點對應一個列表，存儲與它直接相連的所有頂點。
三、鄰接表的具體結構¶
以無向圖爲例，假設頂點0、1、2、3，邊的連接關係如下：
- 頂點0連接頂點1、2、3
- 頂點1連接頂點0、2
- 頂點2連接頂點0、1、3
- 頂點3連接頂點0、2
那麼鄰接表的結構可以表示爲：
頂點0的鄰接表：[1, 2, 3] # 0連接1、2、3
頂點1的鄰接表：[0, 2] # 1連接0、2
頂點2的鄰接表：[0, 1, 3] # 2連接0、1、3
頂點3的鄰接表：[0, 2] # 3連接0、2
用數組表示的話，鄰接表可以寫成：
adj = [
[1, 2, 3], # 頂點0的鄰接點
[0, 2], # 頂點1的鄰接點
[0, 1, 3], # 頂點2的鄰接點
[0, 2] # 頂點3的鄰接點
]
有向圖的鄰接表¶
如果是有向圖（比如頂點0→1，頂點1→2，頂點2→0），鄰接表只需要存儲每個頂點的“出邊”：
頂點0的鄰接表：[1, 2] # 0指向1和2
頂點1的鄰接表：[2] # 1指向2
頂點2的鄰接表：[0] # 2指向0
頂點3的鄰接表：[] # 3沒有出邊
四、鄰接表的實現（以無向圖爲例）¶
用代碼實現鄰接表時，最常用的方式是：
- 用一個數組（或列表）存儲所有頂點的鄰接信息，數組的每個元素對應一個頂點。
- 每個頂點的鄰接信息用一個列表（或鏈表）存儲。
Python實現示例¶
# 假設頂點數爲4（0,1,2,3）
num_vertices = 4
adj = [[] for _ in range(num_vertices)] # 初始化鄰接表，每個頂點對應一個空列表
# 添加邊（無向圖，每條邊(u,v)要同時添加u到v和v到u）
edges = [(0,1), (0,2), (0,3), (1,2), (2,3)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # 無向圖，雙向添加
print(adj) # 輸出：[[1,2,3], [0,2], [0,1,3], [0,2]]
有權圖的鄰接表¶
如果是有權圖，鄰接表的每個元素可以存儲“鄰接點+權重”的元組：
# 有權圖例子：頂點0到1的邊權重是5，0到2的權重是3，0到3的權重是8
edges = [(0,1,5), (0,2,3), (0,3,8), (1,2,2), (2,3,1)]
adj_weighted = [[] for _ in range(num_vertices)]
for u, v, w in edges:
adj_weighted[u].append((v, w))
adj_weighted[v].append((u, w)) # 無向圖雙向
print(adj_weighted)
# 輸出：[[(1,5), (2,3), (3,8)], [(0,5), (2,2)], [(0,3), (1,2), (3,1)], [(0,8), (2,1)]]
五、鄰接表的優缺點¶
- 優點：
- 空間效率高：只存儲實際存在的邊，空間複雜度爲O(V+E)（V是頂點數，E是邊數），適合稀疏圖。
- 遍歷方便：可以快速訪問某個頂點的所有鄰接點。
-
插入和刪除邊也很方便。
-
缺點：
- 查找兩個頂點之間是否有邊需要遍歷鄰接表，時間複雜度爲O(d)（d是該頂點的度數）。
- 對於完全圖（邊數接近V²），鄰接表可能不如鄰接矩陣高效（但這種情況較少見）。
總結¶
圖是數據結構中非常重要的概念，而鄰接表是表示圖的高效方法，尤其適合稀疏圖。掌握鄰接表的表示方法，不僅能幫助我們理解圖的存儲邏輯，還能爲後續學習圖的遍歷算法（如BFS、DFS）和最短路徑算法打下基礎。
希望這篇指南能幫助你快速入門圖的基本概念和鄰接表表示法。實踐中，可以嘗試用鄰接表實現簡單的圖操作，比如遍歷所有鄰接點，或者判斷兩個頂點是否相連。