把问题画成一张图

先找点和边

前面几课处理的数据都是一串数。从这里开始，处理的是关系。

四段题目描述，表面上毫不相干：

• 若干城市之间有公路，问从 A 城能不能开到 B 城。
• 若干课程有先修关系，问能不能排出一个满足全部先修要求的顺序。
• 若干个格子，每步可以走到上下左右相邻的格子，问最少几步到终点。
• 若干个状态，每次操作从一个状态变到另一个状态，问几步能到目标状态。

抽象的做法是问两个问题：这里有哪些「东西」？这些东西之间有哪些「直接联系」？ 第一问的答案就是点，第二问的答案就是边。

• 城市是点，公路是边。
• 课程是点，先修关系是边，方向是「先修课 → 后续课」。
• 格子是点，相邻关系是边。
• 状态是点，一次操作能到达是边。

抽象做完，四道题变成了同一道题：在一个由点和边组成的结构上，从某个点出发能走到哪些点。 后面两课学的遍历算法只要会处理这一件事，四道题就都会了。

有向图与无向图

公路是双向的：能从 A 开到 B，就能从 B 开到 A。先修关系是单向的：学过「变量」才能学「函数」，反过来不成立。

• 无向图：边没有方向，(u, v) 和 (v, u) 是同一条边。
• 有向图：边有方向，u \to v 和 v \to u 是两条不同的边。

这个区别会直接落到代码里。无向图的一条边要在两边各记一次：

def dfs_list(adj, s):
    seen = [False] * len(adj)
    stack = [s]
    seen[s] = True
    order = []
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                stack.append(v)
    return order


def build_undirected_wrong(n, edges):
    adj = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)          # 只加了 u -> v
    return adj


def build_undirected_right(n, edges):
    adj = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)          # 两个方向都加
    return adj


g = [(1, 2), (2, 3), (3, 4)]
w = build_undirected_wrong(4, g)
r = build_undirected_right(4, g)
print('  只加一个方向:', [w[i] for i in range(1, 5)])
print('  两个方向都加:', [r[i] for i in range(1, 5)])
print('  从 4 出发，只加一个方向能到的点:', sorted(dfs_list(w, 4)))
print('  从 4 出发，两个方向都加能到的点:', sorted(dfs_list(r, 4)))

  只加一个方向: [[2], [3], [4], []]
  两个方向都加: [[2], [1, 3], [2, 4], [3]]
  从 4 出发，只加一个方向能到的点: [4]
  从 4 出发，两个方向都加能到的点: [1, 2, 3, 4]

（dfs_list 是下一课要写的遍历，这里先用一个简版，它回答的正是「从某个点出发能走到哪些点」。）

这个 bug 阴的地方在于：从 1 出发看不出问题。 因为边恰好是 1 \to 2 \to 3 \to 4 顺着给的，从起点 1 出发照样能走遍四个点。只有换个起点——从 4 出发——才暴露出来：只能到 [4] 自己。

所以「无向图只记一个方向」这种错，用一组数据试是试不出来的，得换起点试。

边上的数字：带权图

公路有长度，课程有学分，操作有代价。这类数字挂在边上，不挂在点上。

存法很自然：把 adj[u].append(v) 改成 adj[u].append((v, w))，每个元素从「终点」变成「终点与边权」。

带权图的遍历要跟着改：取 v 的时候得写 v, w = item。这一步漏改，后面算出来的一切都错，而且不报错——v 会绑成一个元组，比较和索引都还能跑下去，只是答案不对。

直接存边

最朴素的存法：一个列表，每个元素是一条边。

def build_edges(n, edges):
    return [(u, v) for u, v in edges]


e = build_edges(4, [(1, 2), (2, 3), (3, 4), (4, 1)])
print('  边表:', e)
print('  1 的出边:', [v for u, v in e if u == 1])
print('  找 2 到 3 这条边在不在:', (2, 3) in e)

  边表: [(1, 2), (2, 3), (3, 4), (4, 1)]
  1 的出边: [2]
  找 2 到 3 这条边在不在: True

存法省地方，但用它做任何事都要把整个边表扫一遍：问「1 的出边有哪些」要扫 m 条边，问 m 次就是 O(m^2)。它只在需要把所有边按权值排序的场合才合适（比如第 20 课之后会碰到的最小生成树）。

邻接矩阵

开一个二维数组 adj，adj[u][v] = 1 表示有 u \to v 这条边，0 表示没有。带权图就把 1 换成边权。

def build_matrix(n, edges):
    adj = [[0] * (n + 1) for _ in range(n + 1)]
    for u, v in edges:
        adj[u][v] = 1
    return adj


def build_list(n, edges):
    adj = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)
    return adj


edges = [(1, 2), (2, 3), (3, 4), (4, 1), (1, 3)]
n = 4
m = build_matrix(n, edges)
a = build_list(n, edges)
print('  邻接矩阵:')
for r in range(1, n + 1):
    print('    ', m[r][1:])
print('  邻接表:')
for r in range(1, n + 1):
    print('    ', r, '->', a[r])
print('  矩阵里有多少个格子:', (n + 1) * (n + 1))
print('  表里一共存了几个数:', sum(len(x) for x in a))

  邻接矩阵:
     [0, 1, 1, 0]
     [0, 0, 1, 0]
     [0, 0, 0, 1]
     [1, 0, 0, 0]
  邻接表:
     1 -> [2, 3]
     2 -> [3]
     3 -> [4]
     4 -> [1]
  矩阵里有多少个格子: 25
  表里一共存了几个数: 5

矩阵最大的好处是查一条边在不在只要 O(1)——直接读 adj[u][v]。代价是格子数是 n^2，跟边数无关。

邻接表

邻接表是「每个点挂一个自己的出边列表」：adj[u] 存下所有从 u 出发能直接到的点。

开 n + 1 个空列表，读一条边就往对应列表里塞一个数：

def build_list(n, edges):
    adj = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)
    return adj


adj = build_list(3, [(1, 2), (1, 3)])
print('  1 的出边:', adj[1])
print('  2 的出边:', adj[2])
print('  1 的度:', len(adj[1]))

  1 的出边: [2, 3]
  2 的出边: []
  1 的度: 2

注意 range(n + 1) 这个 + 1。题目里的点通常从 1 开始编号，而列表下标从 0 开始；开 n 个位置就少了一格，遇到编号为 n 的点会直接报错：

def build_buggy(n, edges):
    adj = [[] for _ in range(n)]        # 应该开 n + 1
    for u, v in edges:
        adj[u].append(v)
    return adj


try:
    build_buggy(4, [(1, 2), (2, 3), (3, 4), (4, 1)])
    print('  没报错？')
except IndexError as exc:
    print('  IndexError:', exc)

  IndexError: list index out of range

这类越界是好事——它当场就报。真正麻烦的是另一种：点编号从 0 开始，你却按 n + 1 开、按 1 开始读，程序不报错，只是所有点的编号都错了一位，答案悄悄错掉。

矩阵和表选哪个

差距在数据大起来之后非常明显。n 个点、m 条边，矩阵要 n^2 个格子，表要 m 个位置：

那 100 亿个格子不是「慢一点」的问题，是内存根本装不下、程序直接起不来。

真造一次看看。n = 4000、6000 条边的稀疏图，用 tracemalloc 量：

327 倍。（本机实测；具体数字随 Python 版本与机器变化，看的是倍数这个量级。）

代价还在遍历上。同一个图走一遍，矩阵每次都要把 1 \ldots n 全部检查一遍（O(n^2)），表只走真实存在的边（O(n + m)）：

慢了 191.8 倍。（同样是本机实测，同一台机器同一个图。）

所以选择规则很简单：

• 边数远小于 n^2（稀疏图）→ 邻接表。 竞赛里的图绝大多数是稀疏的，默认选它。
• 需要频繁问「u 到 v 这条边在不在」，且 n 很小 → 邻接矩阵。 稠密图（m 接近 n^2）才用得上。

顺带说一句：邻接矩阵还有一个限制，同一条边只能记一个值。有重边的图（比如「A 到 B 有两条不同长度的路」）用它就必须挑一个留下，而邻接表天然能存下全部。

度与连通

两个只跟图结构有关、不跟算法有关的量，先认下来：

• 度：一个点连出去多少条边。有向图分出度（从它出发的边数）和入度（指向它的边数）。无向图不分方向，只有度数。
• 连通：两个点之间存在一条通路。无向图里，能互相到达的点归成一个连通块；有向图里，能互相到达的点归成一个强连通分量。

度在代码里就是 len(adj[u])。连通要算法来算——下一课就是这件事。

有个容易混的地方：度只数直接相邻，连通看的是能不能绕过去。 一个点可能度为 1（只连着一个邻居），但通过那个邻居连着一大片点。所以「度小的点不重要」这种直觉是错的。

这一课用到的判断

• 抽象就两步：找出有哪些「东西」（点），找出这些东西之间有哪些「直接联系」（边）。
• 无向图的边要在两端各记一次；只记一个方向时，换个起点就会漏掉一大片点。
• 边权挂在边上，存成 (终点, 权值)；带权图的遍历要把 v, w 一起取出来，漏改不报错但答案全错。
• 直接存边适合需要按权值排序的场合（如后面的最小生成树），不适合遍历：问一次出边要扫全部 m 条。
• 邻接矩阵查边 O(1)，代价是 O(n^2) 空间；只适合点少或稠密图，且存不下重边。
• 邻接表是稀疏图的默认选择：O(n + m) 空间，遍历整个图 O(n + m)。
• 点从 1 开始编号时要开 n + 1；开小了当场 IndexError，而编号错位不会报错、只会悄悄算错。
• 度只数直接相邻的边，连通看能不能绕过去；无向图里度数是 len(adj[u])。

• OI Wiki · 图的存储直接存边、邻接矩阵、邻接表、链式前向星四种存法与各自复杂度（本课口径出自这里）
• 《算法导论（第 3 版）》第 22 章 图的基本算法书 · 邻接链表与邻接矩阵的表示、度的定义
• 第 19 课：并查集：谁和谁是一伙的上一课用「集合归属」绕过了遍历，这一课先把图存进内存