你了解鄰接表和鄰接矩陣嗎？圖的世界從這里開(kāi)始！
在算法和數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)中，圖 是一個(gè)比樹(shù)更為復(fù)雜、但也更貼近實(shí)際問(wèn)題的結(jié)構(gòu)。比如社交網(wǎng)絡(luò)、電網(wǎng)布局、地圖導(dǎo)航系統(tǒng)、任務(wù)調(diào)度等，底層都依賴(lài)于圖的結(jié)構(gòu)來(lái)建模。
而在正式編寫(xiě)圖的算法之前，我們必須先搞懂：如何用代碼來(lái)表示圖？
一、什么是圖？
圖（Graph）是一種由**節(jié)點(diǎn)（頂點(diǎn)）和邊（連接）**組成的結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)可以和多個(gè)節(jié)點(diǎn)連接。
圖可以是：
- 有向圖（邊有方向）
- 無(wú)向圖（邊沒(méi)有方向）
- 帶權(quán)圖（邊上有權(quán)重，比如距離、成本）
二、圖的兩種常見(jiàn)表示法
在實(shí)際應(yīng)用中，我們常用以下兩種方式來(lái)表示圖：
1. 鄰接矩陣（Adjacency Matrix）
鄰接矩陣使用一個(gè) N x N 的二維數(shù)組來(lái)表示頂點(diǎn)之間的連接關(guān)系。
# 頂點(diǎn)列表：0, 1, 2
# 邊：0->1，1->2
graph = [
[0, 1, 0], # 0 到 1 有邊
[0, 0, 1], # 1 到 2 有邊
[0, 0, 0] # 2 沒(méi)有出邊
]每個(gè) graph[i][j] = 1 表示節(jié)點(diǎn) i 指向節(jié)點(diǎn) j。
優(yōu)缺點(diǎn)：
優(yōu)點(diǎn) | 缺點(diǎn) |
查找兩點(diǎn)是否相鄰非?？欤∣(1)） | 空間浪費(fèi)嚴(yán)重，尤其是稀疏圖（O(n2)） |
2. 鄰接表（Adjacency List）
鄰接表使用一個(gè)字典（或列表）存儲(chǔ)每個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)列表，更節(jié)省空間。
graph = {
0: [1],
1: [2],
2: []
}每個(gè) key 表示一個(gè)節(jié)點(diǎn)，對(duì)應(yīng)的 value 是它指向的節(jié)點(diǎn)集合。
優(yōu)缺點(diǎn)：
優(yōu)點(diǎn) | 缺點(diǎn) |
更節(jié)省空間，適合稀疏圖（O(n + m)） | 查找相鄰關(guān)系較慢（O(k)） |
三、使用類(lèi)封裝圖結(jié)構(gòu)（推薦做法）
在大型項(xiàng)目或算法中，封裝為類(lèi)能更方便維護(hù)：
class Graph:
def __init__(self, num_nodes):
self.num_nodes = num_nodes
self.adj_list = {i: [] for i in range(num_nodes)}
def add_edge(self, src, dest):
self.adj_list[src].append(dest)
def __str__(self):
return "\n".join(f"{k} -> {v}" for k, v in self.adj_list.items())
# 示例：
g = Graph(3)
g.add_edge(0, 1)
g.add_edge(1, 2)
print(g)輸出結(jié)果：
0 -> [1]
1 -> [2]
2 -> []四、選用哪種表示方式？
情況 | 推薦方式 |
稠密圖（邊接近 n2） | 鄰接矩陣 |
稀疏圖（邊遠(yuǎn)少于 n2） | 鄰接表 |
頻繁查是否存在一條邊 | 鄰接矩陣 |
節(jié)點(diǎn)較多但連接較少（常見(jiàn)場(chǎng)景） | 鄰接表 |
五、小結(jié)
圖的表示是學(xué)習(xí)圖論的第一步，選對(duì)了數(shù)據(jù)結(jié)構(gòu)，算法才能高效執(zhí)行。無(wú)論是遍歷、最短路徑，還是拓?fù)渑判?，理解鄰接表和鄰接矩陣的差異都是基礎(chǔ)能力。
