三种常见表示
邻接矩阵
g[i][j] 表示边权，无边为 0 或 inf。空间 O(V²)，适合 V 较小（≤几百）或稠密图、需要 O(1) 查边、Floyd 全源最短路。
# V 个顶点，初始化无边
g = [[0] * V for _ in range(V)]
g[u][v] = w
g[v][u] = w # 无向邻接表
每个顶点维护邻居列表（或 (v, w) 元组）。空间 O(V+E)，遍历 u 的所有出边 O(度(u))，稀疏图首选。
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # 无向
边列表
仅存 (u, v, w) 三元组，空间 O(E)，适合 Kruskal（按权排序 + 并查集），不适合快速找 u 的所有邻居。
有向 / 加权 / 多图
- 有向图：只加
u → v。 - 权值：表存
(v, weight)或矩阵存g[u][v]=w。 - 自环、重边：列表可允许多条；矩阵后写覆盖或取 min。
并查集（Union-Find）
虽非「图存储」，常与边列表配合判连通分量、检测环、Kruskal。
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
面试选型口诀
| 场景 | 表示 | |---|---| | 一般 BFS/DFS | 邻接表 | | 边少、V 大 | 邻接表 | | 需 O(1) 查边、V≤500 | 矩阵 | | 最小生成树 Kruskal | 边列表 + DSU | | 字符串模式图 | 字典树 / 显式节点对象 |
实现 LeetCode 图题时，先确认顶点编号是 0..n-1 还是需哈希映射；再选 List[] 或 defaultdict，避免重复加边导致 TLE（可去重或题目允许重边）。