数据结构：图

发表于 | 更新于 | 分类于 | 阅读 次
以 Python 内置容器实现图：邻接表（dict + list）与邻接矩阵；有向/加权只是边的语义；BFS/DFS 入口与 NetworkX 选型风险。

图不是新的内置类型，是 「点的邻居名册」。Python 里默认用哈希表 + 动态数组搭 邻接表（adjacency list）；点少边密再考虑 邻接矩阵（adjacency matrix）。

段末注释：图 = 点集 + 边集。有向 / 无向、带权 / 不带权改的是边怎么解释，不是第三种存法。遍历是算法，挂在图上。

图 1　稀疏图用邻居名册（dict→list），稠密图用表格

1. 两种存法

邻接表 邻接矩阵
Python 形状 dict[node, list] 或 dict[node, dict] list[list] 或 方阵
空间 (O(n+m)) (O(n^2))
枚举邻居 (O(\text{度数})) (O(n))
判边 (u\to v) (O(\text{度数}))；权表可 (O(1)) (O(1))
默认场景 几乎所有业务图、算法题 (n) 很小且边很密、或要快速判边

(n) 点数，(m) 边数。现实图几乎都稀疏，先写邻接表。

2. 建图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from collections import defaultdict

def build_undirected(edges):
    """无向不带权图。

    输入：edges 为 (u, v) 可迭代，点可哈希。
    输出：dict[点, list[邻居]]。
    处理：每条边往两端各写一次。
    """
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)
    return g


def build_directed_weighted(edges):
    """有向带权图。

    输入：edges 为 (u, v, w) 。
    输出：dict[点, dict[邻居, 权]]。
    处理：内层 dict 让判边与改权都是期望 O(1)。
    """
    g = defaultdict(dict)
    for u, v, w in edges:
        g[u][v] = w
    return g


def build_matrix(n, edges, directed=False):
    """0..n-1 编号的邻接矩阵。

    输入：n 点数，edges 为 (u, v) 或 (u, v, w)。
    输出：n×n 的 list[list]，无边为 0。
    处理：有权写 w，无权写 1；无向则对称写。
    """
    mat = [[0] * n for _ in range(n)]
    for e in edges:
        u, v, *rest = e
        w = rest[0] if rest else 1
        mat[u][v] = w
        if not directed:
            mat[v][u] = w
    return mat

点 ident 用可哈希对象：str、int、tuple。不要用 list 当点。

矩阵用 [[0]*n]*n 会共享行引用，必须用推导式分行创建（数组专篇踩坑第 1 条）。

3. 遍历入口：宽搜与深搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from collections import deque

def bfs(g, start):
    """广度优先：按层扩张。

    输入：g 为邻接表，start 为起点。
    输出：访问顺序列表。
    处理：队列存待访点，visited 防回头。
    """
    seen, q, order = {start}, deque([start]), []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            if v not in seen:
                seen.add(v)
                q.append(v)
    return order


def dfs(g, start):
    """深度优先：显式栈，避免深递归。

    输入 / 输出：同 bfs。
    处理：栈后进先出；入栈前标记，防止同一点反复压栈。
    """
    seen, st, order = {start}, [start], []
    while st:
        u = st.pop()
        order.append(u)
        for v in reversed(list(g[u])):
            if v not in seen:
                seen.add(v)
                st.append(v)
    return order
算法 结构 典型用途
广度优先搜索（Breadth-First Search，BFS） deque 无权最短路、分层
深度优先搜索（Depth-First Search，DFS） 栈或递归 连通块、拓扑、环检测
Dijkstra 堆 + 距离表 非负权最短路
Union-Find 并查集 无向连通、Kruskal

无权最短路用 BFS，不要 Dijkstra。负权才考虑 Bellman-Ford，标准库没有现成函数。

4. 有向图专题（最小集）

  • 入度表：indeg[v] += 1，Kahn 拓扑：入度为 0 的进队列。
  • 环：有向图 DFS 三色（未访 / 栈中 / 已完）或拓扑后还剩点。
  • 反向图：扫边 (u,v) 建 g[v].append(u)，强连通、回溯路径用。

这些是算法，图的存储仍然是邻接表。

5. 踩坑

  1. 无向边只写一次：遍历会丢反向。建图就写对称，或约定「只存 u < v」并在遍历时补。
  2. visited 放晚了：宽搜在出队时才标记，队列会爆。入队即标。
  3. 递归 DFS 深图：默认递归上限 1000。深链改显式栈。
  4. 邻接 list 里判边：v in g[u] 是 (O(\text{度数}))。频繁判边把邻居改成 set 或内层 dict。
  5. 矩阵当稀疏大图：(n=10^5) 的 (n^2) 内存直接炸。

6. 自检

  1. 什么时候邻接矩阵优于邻接表？
  2. 有向带权图用 dict[u][v] = w 比 dict[u] = [(v,w), …] 多了哪一种 (O(1))？
  3. 无权最短路为什么是 BFS 不是堆？
  4. [[0]*n]*n 建矩阵会怎样？

7. 社区口径与风险

内置 dict + list / deque / heapq 能覆盖教学与大部分业务图。需要画图、算法电池（最短路、匹配、中心性）时社区方案是 NetworkX；风险是纯 Python、大图慢、内存胖。性能敏感路径看 graph-tool、igraph 或自己用 CSR 压缩行存储（SciPy csr_matrix）。不要为「我有一张图」先 pip install networkx 再写三行 BFS。

-------------本文结束感谢您的阅读-------------