图算法：从表示、遍历到连通性与路径选择

数组擅长表达位置，树擅长表达层级，但现实中的关系往往没有这么整齐。一个路口可以连向多条道路，一个任务可能同时依赖多个前置任务，一个网页也会被许多页面引用。遇到这种“多对多”的连接，我们需要图。

图算法最容易学乱的地方，不是代码长，而是几个看起来相似的问题其实在求不同目标：BFS 求的是无权图中的最少边数，拓扑排序处理的是有向无环图中的先后约束，最小生成树让所有顶点以最小总成本连通，最短路径则关心从一个起点到各处的路径代价。如果问题没有先分清，算法选得越熟练，结果反而可能错得越隐蔽。

这篇文章从图模型开始，依次讲邻接表与邻接矩阵、广度优先搜索、深度优先搜索、拓扑排序和强连通分量，最后把最小生成树与单源最短路径放到同一张选择表中。每一种算法都会说明它维护什么状态、为什么正确、复杂度是多少，以及哪些输入条件不能越过。

先把现实关系翻译成图

一张图记为 $G=(V,E)$。$V$ 是顶点集合，表示研究对象；$E$ 是边集合，表示对象之间的关系。通常用 $|V|$ 表示顶点数，用 $|E|$ 表示边数。算法复杂度中的 $V$ 和 $E$ 常常是这两个数量的简写。

如果边没有方向，无向边写成集合 $\lbrace u,v\rbrace$，它表示 $u$ 与 $v$ 之间的对称关系。如果边有方向，有向边写成有序对 $(u,v)$，它只表示从 $u$ 指向 $v$。在有向图里， 与 是两条不同的边。

边还可以携带权重 $w(u,v)$。权重不一定是空间距离，也可以是耗时、费用、损耗或风险。只要一条路径的总代价等于沿途边权之和，就可以把它放进常见的路径模型中：

其中路径 $p=\langle v_0,v_1,\ldots,v_k\rangle$，每一对相邻顶点之间都有对应方向的边。路径长度是边的数量 ；路径权重则是这些边权之和。两者只有在每条边权都相同的时候才表达同一个目标。

度、路径与环

无向图中，顶点 $v$ 的度 $\deg(v)$ 是与它关联的边数。一条普通无向边会给两个端点各贡献一次度，因此：

有向图要区分出度与入度。$\deg^+(v)$ 统计从 $v$ 出发的边，$\deg^-(v)$ 统计指向 $v$ 的边。所有顶点出度之和、所有顶点入度之和都等于 $$。

路径中不重复顶点时，它是简单路径。起点与终点相同、并且至少经过一条边时形成环。无向图中两个顶点之间互相可达，表示它们属于同一个连通分量；整张无向图只有一个连通分量时称为连通图。对有向图来说，“从 $u$ 能到 $v$”不代表“从 $v$ 能回到 $u$”，所以还要用强连通描述双向可达。

简单图、稀疏图与稠密图

简单图不含自环，也不在同一对顶点之间放多条重复边。具有 $n$ 个顶点的简单无向图最多有 $n(n-1)/2$ 条边，简单有向图若不允许自环，最多有 $n(n-1)$ 条边。边数远小于顶点对数量时，我们说图是稀疏的；边数接近上限时，图是稠密的。

“稀疏”没有一条对所有工程场景都适用的绝对分界线。真正有用的判断是：当前边数能否让 $O(V+E)$ 的存储和遍历明显优于 $O(V^2)$，以及业务是否频繁查询任意两点之间有没有边。

建模时先问四个问题

看到关系数据时，可以按下面的顺序检查：

1. 顶点究竟代表什么对象？不要把“路口”和“道路”混成同一层对象。
2. 关系有没有方向？好友关系通常对称，关注关系通常不对称。
3. 边权能否沿路径相加？容量、可靠性等指标未必直接适合做加法。
4. 允许自环、重边和不可达顶点吗？这些边界会影响表示和算法输出。

邻接表与邻接矩阵怎样选择

图是抽象关系，程序还要决定怎样把关系放进内存。最常用的两种表示是邻接表和邻接矩阵。它们表达的是同一张图，但把成本放在了不同操作上。

邻接表只保存实际存在的边

邻接表为每个顶点 $u$ 保存一个列表 Adj[u]。有向图中，列表通常包含所有满足 $(u,v)\in E$ 的顶点 $v$，也就是 $u$ 的出邻居。无向图的一条边 $\lbrace u,v\rbrace$ 要在 Adj[u] 中存一次 $$，也在 中存一次 。

因此，有向图全部邻接表的长度之和为 $|E|$，无向图为 $2|E|$。连同 $|V|$ 个表头，空间复杂度是：

遍历 $u$ 的所有邻居需要 $\Theta(\deg^+(u))$ 时间。若列表没有额外索引，查询边 $(u,v)$ 是否存在，最坏也要扫描 Adj[u]。添加边可以做到常数时间或摊还常数时间，删除边则通常先要定位目标。

加权图可以把每个表项写成 (邻居, 权重)。顶点颜色、距离、父节点、发现时间等算法属性不必硬塞进边表，可以用与顶点编号平行的数组保存。这样图结构与某一次算法运行的状态不会混在一起。

邻接矩阵把所有顶点对都留出位置

若顶点编号为 $0,1,\ldots,n-1$，邻接矩阵是一个 $n\times n$ 的矩阵 $A$。无权图通常定义：

查询任意一条边只需访问一个单元格，时间为 $\Theta(1)$；但列出某个顶点的邻居必须扫描一整行，时间为 $\Theta(V)$。矩阵无论实际有多少边，都需要 $\Theta(V^2)$ 空间。

无向图的矩阵关于主对角线对称，因为 $A[i][j]=A[j][i]$。有向图的转置图 $G^T$ 把所有边反向，它的邻接矩阵正好是 $A^T$。加权矩阵可以在单元格中保存权重，但“没有边”的标记必须与合法权重区分。如果权重允许为 0，就不能再用 0 同时表示不存在。

操作成本对照

如果既想保留邻接表的紧凑性，又需要较快查边，可以把每个邻接集合实现成哈希表或平衡树。不过这会增加常数、内存和顺序遍历成本。表示的选择仍要跟实际操作频率一起判断。

下面的交互把同一张有向图同时转换成邻接表和邻接矩阵。修改边后点击“重新生成”，可以直观看到不存在的顶点对为什么仍占据矩阵单元格。

转置图的线性构造

邻接表构造转置图时，新建 $|V|$ 个空表，再扫描每一条边 $(u,v)$，把 $u$ 加进转置图的 AdjT[v]。每个顶点初始化一次，每条边处理一次，复杂度为 $\Theta(V+E)$。

TRANSPOSE(G)
    为每个顶点 v 创建空表 AdjT[v]
    for 每个顶点 u:
        for 每个 v in Adj[u]:
            AdjT[v].append(u)
    return AdjT

广度优先搜索按距离扩展边界

给定源点 $s$，广度优先搜索（BFS）先发现与 $s$ 相距 1 条边的顶点，再发现相距 2 条边的顶点，按层向外扩展。它既适用于有向图，也适用于无向图；它只会访问从 $s$ 可达的顶点。

BFS 为每个顶点维护三个核心属性：

• color：白色表示未发现，灰色表示已发现但邻接表还没扫描完，黑色表示邻接表已处理完。
• d[v]：当前得到的从 $s$ 到 $v$ 的最少边数，未发现时为无穷大。
• parent[v]：第一次发现 $v$ 时从哪个顶点到达，用于构造 BFS 树和恢复路径。

队列是层序扩展的关键。顶点在第一次变灰时立刻入队，而不是等出队时才标记，否则同一顶点可能被多个前驱重复加入队列。

BFS(G, s)
    for 每个顶点 v:
        color[v] = 白
        d[v] = ∞
        parent[v] = 空
    color[s] = 灰
    d[s] = 0
    Q = 只包含 s 的队列
 
    while Q 非空:
        u = Q.dequeue()
        for 每个 v in Adj[u]:
            if color[v] == 白:
                color[v] = 灰
                d[v] = d[u] + 1
                parent[v] = u
                Q.enqueue(v)
        color[u] = 黑

队列不变式与最短边数

BFS 的核心不变式是：每次检查 while 条件时，队列恰好保存所有灰色顶点。更细一点，队列中的距离从队首到队尾不递减，并且最多只出现相邻的两层距离。若队首距离为 $k$，队尾距离不会超过 $k+1$。

为什么这能得到最少边数？设 $v$ 是通过 $u$ 第一次发现的，于是 d[v]=d[u]+1，这给出了一条真实路径，所以估计不会凭空小于某条可行路径长度。另一方面，队列保证所有距离更小的层都先被处理。如果存在一条边数更少的路径，它的倒数第二个顶点必然更早出队，并会更早发现 $v$，这与“当前才第一次发现”矛盾。

最终，对每个从 $s$ 可达的顶点 $v$，都有：

这里 $\delta(s,v)$ 表示从 $s$ 到 $v$ 的最少边数。parent 边组成一棵以 $s$ 为根的 BFS 树，其中从根到任意顶点的树路径都是原图中的一条最短边数路径。最短路径可能不唯一，所以邻接表顺序可能改变 parent，却不会改变 d。

下面可以逐步观察队列与距离层怎样变化。黄色节点在队列中，绿色节点已经完成，虚线框中的数字是从源点 A 出发的最少边数。

复杂度、路径恢复与适用边界

邻接表下，每个顶点最多入队一次，每条边按邻接表出现次数被检查，时间为 $\Theta(V+E)$，额外状态为 $\Theta(V)$。邻接矩阵下，每处理一个顶点都要扫描一整行，时间变成 $\Theta(V^2)$。

恢复从 $s$ 到 $v$ 的路径时，从 parent[v] 反向走到 $s$，再把序列倒转。成本与输出路径的顶点数成正比。若 parent[v] 为空且 $v\ne s$，则 $v$ 从 $s$ 不可达。

BFS 适合以下任务：

• 无权图或每条边代价相同的最短路径；
• 判断二分图，可按距离奇偶给顶点染两种颜色；
• 计算社交关系中的最少连接层数；
• 从多个源同时扩散，把所有源点以距离 0 一起入队即可。

深度优先搜索记录嵌套结构

深度优先搜索（DFS）总是沿着最近发现、仍有未探索出边的顶点继续深入。走到没有新邻居时，它回退到上一个尚未完成的顶点。若一次搜索结束后还有白色顶点，就从其中一个重新开始，于是整张图得到的不是一棵树，而是一片 DFS 森林。

DFS 同样使用白、灰、黑三种状态，但它还为每个顶点记录两个时间戳：

• discover[u]：第一次发现 $u$ 的时间；
• finish[u]：$u$ 的所有出边都处理完的时间。

对每个顶点都有 discover[u] < finish[u]。灰色顶点恰好对应当前递归调用栈，它们从树根到当前顶点形成一条祖先链。

DFS(G)
    for 每个顶点 u:
        color[u] = 白
        parent[u] = 空
    time = 0
    for 每个顶点 u:
        if color[u] == 白:
            DFS-VISIT(u)
 
DFS-VISIT(u)
    time = time + 1
    discover[u] = time
    color[u] = 灰
    for 每个 v in Adj[u]:
        if color[v] == 白:
            parent[v] = u
            DFS-VISIT(v)
    color[u] = 黑
    time = time + 1
    finish[u] = time

递归实现与显式栈实现都可以达到 $\Theta(V+E)$ 时间。若担心图很深导致调用栈溢出，可以用栈保存 (顶点, 下一个待处理邻居位置)，这样回退时才不会从邻接表开头重复扫描。

时间区间不会交叉相压

把每个顶点对应成区间 $[discover[u],finish[u]]$，任意两个顶点的区间只会出现两种关系：完全分离，或者一个完整包含另一个。不会出现两个区间只交叉一半的情况。

若 $v$ 是 $u$ 在 DFS 树中的真后代，则：

这就是括号嵌套性质。发现顶点相当于写左括号，完成顶点相当于写右括号，整个搜索历史会形成合法的括号序列。它让我们能够只比较时间戳，就判断 DFS 树中的祖先关系。

另一个有用事实是白路径性质：发现 $u$ 的那一刻，$v$ 最终成为 $u$ 的后代，当且仅当此时存在一条从 $u$ 到 $v$、全部由白色顶点组成的路径。后面的拓扑排序与强连通分量都依赖这种“DFS 会吃完整条白路径”的能力。

有向边可以分成四类

DFS 探索有向边 $(u,v)$ 时，可以结合 $v$ 的颜色与时间戳分类：

• 树边：$v$ 是白色，通过这条边第一次发现 $v$；
• 后向边：$v$ 是灰色，边从后代指向当前递归栈中的祖先，自环也属于这一类；
• 前向边：$v$ 已是黑色，并且是 $u$ 的后代，但这条边不是树边；
• 横向边：连接没有祖先后代关系的两个顶点，可以跨 DFS 树。

在无向图中，同一条边会从两个方向出现在邻接表里。按第一次遇到时分类，每条边只会是树边或后向边，不会出现前向边和横向边。实现时还要避免把“指回父节点的那份反向表项”误判成一个有意义的环。

下面的交互使用一张固定有向图。每点击一次，执行一个 DFS 事件；节点会显示发现/完成时间，事件日志会说明当前动作。

DFS 能直接回答什么

邻接表下，初始化所有顶点是 $\Theta(V)$，每个邻接表项检查一次，总时间为 $\Theta(V+E)$，状态空间为 $\Theta(V)$，递归栈最深可达 $\Theta(V)$。

DFS 森林可以直接标识无向图的连通分量：每次从白色顶点启动的新 DFS 树，就是一个连通分量。后向边还能判断有向图是否有环；完成时间则给出拓扑顺序和强连通分量算法所需的处理次序。进一步维护子树能回到的最早发现时间，还可以在线性时间寻找无向图的割点和桥。

拓扑排序把依赖关系排成线性顺序

有向无环图通常简称 DAG。它适合表示“必须先做什么”的约束：边 $(u,v)$ 表示 $u$ 必须出现在 $v$ 之前。拓扑排序要找出所有顶点的一个线性排列，使每条有向边都从排列左侧指向右侧。

只有 DAG 才存在拓扑序。如果图中有环，例如 $A\to B\to C\to A$，三个任务都要求另一个先完成，任何线性次序都会违反至少一条边。

按 DFS 完成时间逆序输出

一种做法是在 DFS 中完成顶点时把它插到链表头部，等价于按 finish 从大到小排列。

TOPOLOGICAL-SORT(G)
    order = 空链表
    执行 DFS(G)
    每当顶点 u 完成时:
        order.push_front(u)
    如果 DFS 发现后向边:
        报告“存在环，没有拓扑序”
    否则返回 order

正确性的关键是：在 DAG 中不可能出现后向边。对任意边 $(u,v)$，DFS 探索它时，$v$ 只能是白色或黑色。若是白色，$v$ 会成为 $u$ 的后代并先完成；若是黑色，$v$ 已经完成。两种情况都得到：

所以按完成时间递减排列时，$u$ 一定在 $v$ 前面。

不断移除入度为零的顶点

另一种做法先计算所有入度，把入度为 0 的顶点放入队列。每次输出一个顶点并“删除”它的所有出边，也就是把每个出邻居的入度减 1；新的 0 入度顶点继续入队。

这个过程维护的不变式是：队列中的顶点在剩余图里没有任何未满足的前置条件。若最终输出顶点数小于 $|V|$，剩余部分每个顶点入度都大于 0，其中必然含环。

两种方法的时间复杂度都是 $\Theta(V+E)$。DFS 版本自然提供完成时间；入度版本更适合逐步安排任务，也更容易根据队列大小观察当前有多少个可选任务。拓扑序不一定唯一：某一步若有多个 0 入度顶点，选择次序不同就可能得到不同的合法结果。若每一步队列都恰好只有一个顶点，拓扑序才是唯一的。

下面的实验使用零入度方法。可以选择无环依赖或含环依赖，再逐步移除任务。

拓扑序不是按名称排序

拓扑排序只保证边表达的偏序约束，不会自动优化总工期、资源冲突或字典序。如果任务可以并行，拓扑序只是一个合法线性化结果；真正的调度还可能需要任务时长、机器数量和优先级。

强连通分量把有向环压缩成 DAG

在有向图中，若 $u$ 能到达 $v$，并且 $v$ 也能到达 $u$，就说两者互相可达。一个强连通分量是极大的互相可达顶点集合。“极大”表示不能再加入分量外的任何顶点而仍保持两两互相可达。

单个顶点也可以构成强连通分量。一个自环不会改变它属于单点分量的事实，但会影响“图中是否有环”的判断。无向图不需要强连通这个额外概念，因为无向边天然可以双向经过，无向图直接讨论连通分量即可。

分量图一定无环

把每个强连通分量缩成一个超级顶点，若原图存在一条从分量 $C_i$ 指向分量 $C_j$ 的边，就在超级顶点之间连边，得到分量图。

分量图一定是 DAG。假设两个不同分量之间构成有向环，那么沿环可以从任一分量到达另一个分量并再返回，环上的顶点就应该属于同一个更大的强连通分量，这与分量已经极大矛盾。

压缩这一步很有价值。原图内部可能有大量环，但分量图没有环，于是后续可以在分量图上做拓扑排序、动态规划或依赖传播。

两次 DFS 的完整过程

下面的方法在线性时间内找出所有强连通分量：

STRONGLY-CONNECTED-COMPONENTS(G)
    在 G 上执行 DFS，记录每个顶点的完成时间 finish
    构造转置图 GT，把所有边反向
    按第一遍 finish 从大到小遍历顶点
    在 GT 上执行第二遍 DFS
    第二遍得到的每一棵 DFS 树就是一个强连通分量

第一遍 DFS 得到的是分量之间的完成先后。若原图中有边从分量 $C$ 指向不同分量 $C'$，那么第一遍搜索得到的分量最大完成时间满足 $f(C)>f(C')$。转置以后，跨分量边方向反过来。

第二遍从第一遍完成时间最大的未访问顶点开始。在转置图中，这个起始分量没有通向其他未访问分量的边，因此 DFS 不会越界；与此同时，分量内部仍然互相可达，所以整块都会被访问。删去这块后，同样的理由可以反复应用到剩余分量。

不变式、复杂度与实现细节

第二遍搜索的不变式可以表述为：每次选择新的 DFS 根时，所有已输出树都是完整且互不重叠的强连通分量；从当前根出发，只能到达它自己的未访问分量，跨分量出边只会指向已经完成的分量。

第一遍 DFS 是 $\Theta(V+E)$，构造转置图是 $\Theta(V+E)$，第二遍 DFS 仍是 $\Theta(V+E)$，总时间为 $\Theta(V+E)$，额外空间也是 。若系统已经同时维护正向与反向邻接表，就可以省去临时构造转置图的步骤，但仍要付出保存两份边表项的空间。

构造分量图时，要注意去重。原图可能有很多条边从 $C_i$ 指向 $C_j$，压缩后通常只保留一条分量边。可以扫描原边，把 (component[u], component[v]) 放入集合；当两个分量编号相同时，这条边属于分量内部，不加入分量图。

加权图先分清生成树与最短路径

图带上权重后，最常见的两个目标是“让所有点连起来的总成本最低”和“从一个起点到各点的路径代价最低”。前者是最小生成树，后者是单源最短路径。它们都可能用到优先队列，也都可能长成一棵树，但优化目标完全不同。

最小生成树优化整张网络的总边权

给定连通、无向、加权图 $G=(V,E)$，生成树是连接所有顶点且不含环的边集。任意生成树都有 $|V|-1$ 条边。最小生成树（MST）要让树中所有边权之和最小：

MST 不指定源点，也不保证任意两点之间的树路径是原图最短路径。边权可以为负数；只要图是无向且连通，Kruskal 和 Prim 的贪心依据仍然成立。若图不连通，则不存在覆盖全部顶点的一棵生成树，但可以对每个连通分量求最小生成森林。

两种经典算法都依赖割的安全边性质。一个割 $(S,V-S)$ 把顶点分成两部分。若当前已选边 $A$ 没有跨过这个割，那么跨割的最轻边可以安全加入：存在一棵包含 $A$ 与这条边的最小生成树。证明思路是交换。若某棵最优树没有这条轻边，把它加入会形成环；环上必有另一条边跨过同一个割，删除那条不更轻的边，仍得到总权重不增的生成树。

Kruskal 从空森林开始，按权重从小到大检查边。若边的两个端点属于不同连通分量，就加入并合并两个集合；否则加入会成环，跳过。用并查集维护分量，排序主导复杂度：

Prim 从任意根开始，只维护一棵正在增长的树。每次选择连接“树内”与“树外”的最轻边，把新顶点纳入。邻接表配二叉最小堆时为 $O(E\log V)$；稠密图使用邻接矩阵和线性扫描取最小键值时可以实现为 $O(V^2)$。

两者的不变式都是“当前边集包含在某棵 MST 中”，但形状不同：Kruskal 的当前结果是一片森林，Prim 的当前结果始终是一棵树。边权相同会让 MST 不唯一，算法仍可返回任意一棵最优树。

单源最短路径优化每个目标点的路径

单源最短路径给定源点 $s$，要求对每个顶点 $v$ 计算：

若不可达，距离为无穷大。若从 $s$ 可达某个负权环，并且还能从环到达 $v$，就可以反复绕环让路径权重无限下降，此时不存在有限的最短路径。

最短路径的核心操作是松弛。d[v] 始终是当前已知路径给出的上界。检查边 $(u,v)$ 时，尝试用经过 $u$ 的路径改善它：

RELAX(u, v, w)
    if d[v] > d[u] + w(u,v):
        d[v] = d[u] + w(u,v)
        parent[v] = u

初始化时 d[s]=0，其余为无穷大。关键不变式是上界性质：始终有 $d[v]\ge\delta(s,v)$；一旦某个估计达到真实最短距离，后续松弛不会把它改坏。各算法的差别，主要在于用什么顺序、多少次松弛边。

按输入条件选择算法

DAG 最短路径先拓扑排序，再按拓扑序处理每个顶点的所有出边。所有可能的前驱都先于当前顶点被处理，所以每条边只需松弛一次。DAG 没有环，因此可以安全包含负权边。

Dijkstra 每次从尚未定型的顶点中取 d 最小者，将其距离永久定型，再松弛它的出边。非负边保证最短路径后半段不会把一个更远的未定型顶点突然变得更近。只要允许一般负边，这个论证就会失效，已经定型的距离可能被后来路径改小。

Bellman-Ford 连续做 $|V|-1$ 轮，每轮松弛全部边。没有可达负环时，最短路径总能选成至多含 $|V|-1$ 条边的简单路径；第 $i$ 轮足以把使用至多 $i$ 条边的改进传播出去。完成这些轮次后再扫描一遍，若仍有边能被松弛，就存在从源点可达的负权环。

需要特别区分：图中存在负权环，不代表当前源点问题一定无解。只有源点能够到达的负环才会影响这次单源最短路径；不可达区域里的负环不会改变从 $s$ 出发的距离。

相似的优先队列，不同的键

Prim 与 Dijkstra 的代码骨架很像：都从一个集合向外扩张，都用最小优先队列，也都更新邻居的键。区别藏在键的含义里：

• Prim 的 key[v] 是把 $v$ 接到当前树上的最轻单边权重；
• Dijkstra 的 d[v] 是从源点走到 $v$ 的完整路径权重。

因此，不能因为实现相似就互换。MST 的一条边是否安全取决于割；最短路径的一次定型是否安全取决于从源点的距离与非负权条件。