算法 08：图遍历、最短路、拓扑排序与最小生成树

同一张道路图，可以问“哪些地方能到”“到目的地的最短距离是多少”，也可以问“用最少的总造价把所有地点连起来”。它们都处理顶点和边，优化的对象却不同。用队列、优先队列或并查集之前，先把问题说清楚，才能知道何时可以确定一个答案。

本篇围绕一张小图，完整展开遍历、距离松弛、依赖消除和安全选边的过程。配套完整 C++17 程序包含 Floyd–Warshall 对照、生成森林枚举和边界验证；运行入口见学习路线。

一、先区分四种问题

DFS 适合展开可达区域、维护递归关系和分析环，它通常不保证第一次找到的路径最短。存在负边时，Dijkstra 的“取出后即可确定距离”不再有保证，需要 Bellman–Ford 等符合输入条件的算法。

下面的顶点用 A…F 表示，代码中映射为 0…5。这是有向图；A→B 不意味着允许从 B 返回 A。

例如 A→B→D→E 有 3 条边、总权重 10；A→C→B→D→E 有 4 条边、总权重 7。最少边数和最小权重已经给出不同的答案。

怎样存，决定怎样数成本

邻接表把每个顶点的出边放在一个列表里。

using Weight = std::int64_t;
struct Arc { std::size_t to; Weight weight; };
using Graph = std::vector<std::vector<Arc>>;

const Graph graph{
    {{1,6},{2,1}}, // A
    {{3,1}},       // B
    {{1,2},{3,5}}, // C
    {{4,3}},       // D
    {}, {}        // E, F
};

设顶点数为 V、边数为 E，存储占 O(V+E)。有向边存一次；无向边用于遍历时通常在两个端点各存一次。下面的复杂度都按邻接表衡量，算法辅助空间另外说明。

二、BFS 与 DFS：何时算“已经发现”

BFS 的第一次发现，确定的是层数

从 A 开始，把所有边暂时视为代价 1。先发现 B、C，距离为 1；处理 B 时发现 D，距离为 2；处理 D 时发现 E，距离为 3。F 始终不可达。

关键是发现邻居时就记录距离并入队。如果只在出队时标记，B 和 C 都可能把 D 加入队列；同一顶点会被重复处理，队列大小与复杂度分析也随之改变。

std::vector<std::optional<std::size_t>> distance(graph.size());
std::queue<std::size_t> pending;
distance[source] = 0;
pending.push(source);
while (!pending.empty()) {
    const auto u = pending.front();
    pending.pop();
    for (const auto& edge : graph[u]) {
        if (distance[edge.to]) continue; // 已发现，包括合法的距离 0
        distance[edge.to] = *distance[u] + 1;
        pending.push(edge.to);
    }
}

optional 的真假表示“有没有值”，因此保存 0 的 source 仍然是已发现状态。它也把“不可达”和“距离为 0”分开。

队列中的顶点按非递减层数排列。发现一个距离 k+1 的顶点时，所有更早的层都已得到处理机会；如果存在更短路径，它就应该从更早的层被发现。因此第一次发现给出的就是最短边数。

每个顶点最多入队一次，每条可达出边扫描一次，加上初始化，时间 O(V+E)，辅助空间 O(V)。这段代码故意忽略权重，所以本例到 E 得到 3，不能解释成道路距离为 3。

DFS 沿一条分支深入，再回来展开其他分支

递归 DFS 在进入一个顶点时标记它，然后依次递归处理未发现的邻居。沿本例的邻接表顺序，会先走 A→B→D→E，回退后再访问 C。它最先看到的 A 到 E 路径权重为 10，不能据此宣布最短距离。

void dfs(std::size_t u,
         const std::vector<std::vector<std::size_t>>& adjacency,
         std::vector<bool>& seen) {
    seen[u] = true;
    for (auto v : adjacency[u])
        if (!seen[v]) dfs(v, adjacency, seen);
}

标记保证每个顶点只展开一次，所以总时间仍为 O(V+E)。seen 加递归调用栈占 O(V) 辅助空间；链状图可能递归 V 层。深图宜改用显式栈；需要保留递归进入、返回事件时，栈帧还要保存“下一条待检查的出边”。

遍历一次起点，不等于遍历完整张图

对无向图，在外层枚举所有顶点，每遇到尚未发现的顶点就启动一次 BFS 或 DFS，就能得到连通分量。下面的 adjacency 必须将每条无向边双向存储。

std::size_t components = 0;
std::vector<bool> seen(adjacency.size(), false);
for (std::size_t root = 0; root < adjacency.size(); ++root) {
    if (seen[root]) continue;
    ++components;
    dfs(root, adjacency, seen);
}

把本例各条边改为无向边后，A 到 E 属于一个分量，F 单独属于另一个分量，结果为 2。空图结果为 0；孤立点也算一个分量。

有向图需要说明是在求弱连通还是强连通。弱连通要忽略方向；强连通要求顶点之间彼此可达，通常使用 Kosaraju 或 Tarjan。直接把上面的外层 DFS 套在有向图上，得到的是依赖起点顺序的遍历森林，不能当作强连通分量数。

三、Dijkstra：距离可以改进，确定答案的顺序不能乱

松弛是在比较一个完整候选路径

dist[v] 保存当前找到的最短路径长度。若已经找到 A 到 u 的路径，再经过 u→v，就得到候选 dist[u]+w(u,v)。候选更小时，更新 dist[v]，同时记录 parent[v]=u。

这一步叫松弛。更新后的数值仍对应一条真实路径，所以它是最短距离的上界；尚未找到路径时显示为 ∞。不是把某条边单独的权重当作到终点的距离。

最终到 E 的最短路径为 A→C→B→D→E，总权重 1+2+1+3=7。F 的 ∞ 表示不可达。

优先队列里可以留着旧版本

C 改进 B 的距离时，队列里原本有 (6,B)。C++ 的 priority_queue 不直接提供修改任意条目的 decrease-key 接口；简单实现可以再放入 (3,B)，保留旧条目，出队时核对版本。

using Entry = std::pair<Weight, std::size_t>; // 距离、顶点
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> pending;
dist[source] = 0;
pending.emplace(0, source);
while (!pending.empty()) {
    const auto [du, u] = pending.top();
    pending.pop();
    if (!dist[u] || du != *dist[u]) continue; // 跳过过期条目
    for (const auto& edge : graph[u]) {
        const auto candidate = checked_add(du, edge.weight);
        if (!dist[edge.to] || candidate < *dist[edge.to]) {
            dist[edge.to] = candidate;
            parent[edge.to] = u;
            pending.emplace(candidate, edge.to);
        }
    }
}

本例在处理 D（4）后，还会弹出 B（6）、D（6）。它们与当前距离 3、4 不符，直接跳过；这里“取出顺序”包含旧条目，但“有效确定顺序”仍为 A、C、B、D、E。

更新条件用严格 <。零权边合法；相等距离无需反复入队。重复边也合法，每条边各扫描一次；非负自环不会改进已有距离。

为什么最小的当前距离可以确定

设有效取出的 u 是尚未确定的顶点中当前距离最小的。如果有一条更短路径，它从起点走来时一定经过某个最早的未确定顶点 x；此前的顶点已确定并松弛过到 x 的边。

因此 dist[x] 不会大于这条假想路径到 x 的长度。剩余边非负，路径到 x 的长度又不会大于整条路径到 u 的长度。于是 dist[x] 应比 dist[u] 更小，与“先取出了 u”矛盾。非负条件正是在这一步发挥作用。可进一步核对 MIT 的 Dijkstra 讲义。

例如 S→X=2, S→Y=5, Y→X=-4，X 可能先以 2 被取出，但实际上到 X 的距离是 1。允许重新入队的变体有时还会得到正确结果，但此时已经失去 Dijkstra 的确定顺序与复杂度保证；不能用个别运行结果证明负边可用。

辅助空间为什么不总是 O(V)

本篇用保留旧条目的二叉堆实现。每条边最多引起一次成功松弛，队列可能积累 O(E) 个条目，因此时间写作 O(V+E log(E+1))，辅助空间 O(V+E)。若限制为简单图，常见写法是 O((V+E) log V)。支持 decrease-key、每个顶点只保留一个条目的堆实现，空间口径又不同。

完整程序先校验全图非负边权和端点，包括不可达区域。距离用 optional<int64_t>，这样合法距离 INT64_MAX 也不会和不可达哨兵混淆。加法通过 checked_add 检查；本示例只要扫描到的候选和超出 int64_t 范围，就报告错误，调用者应选择可表示的权重规模。

保存前驱，恢复实际路线

松弛时保存 parent，从 E 反向得到 E←D←B←C←A，反转即为路径。

std::vector<std::size_t> path;
if (dist[target]) {
    for (auto u = std::optional<std::size_t>{target}; u; u = parent[*u])
        path.push_back(*u);
    std::reverse(path.begin(), path.end());
}

起点到自己返回只含起点的路径；不可达返回空路径。多条最短路径并存时，这段实现返回其中一条，不保证字典序最小。

四、Bellman–Ford：负边改变了确定答案的方法

Bellman–Ford 不再靠当前最小距离一次确定顶点，而是反复扫描全部边。初始化起点为 0、其余不可达，最多执行 V−1 轮松弛；某轮没有任何更新时可以提前结束。

重复至多 V-1 轮：
    对每条边 u→v：
        若 u 可达且 dist[u]+w < dist[v]，更新 dist[v]
再扫描所有边：
    若仍有一条从可达 u 出发的边能够改进，报告可达负环

为什么是 V−1？没有可达负环时，总能选出一条不重复顶点的最短路径，边数至多 V−1。每轮完整扫描至少能够把正确距离向这条路径推进一条边；某些边扫描顺序还会在同轮推进更多。时间 O(VE)，距离与前驱的辅助空间 O(V)。

负环不是“存在一条负边”。例如 S→A=2, A→B=-3 的最短距离仍然定义良好；如果再加 B→A=1，A 与 B 之间的环总权重为 −2，可以反复绕圈让路径越来越短，不存在有限最小值。

需要区分两件事：从 S 到不了的负环不会影响 S 的最短路；从可达负环还能到达的顶点才会受到无限降低的影响。额外一轮发现更新后，可以从更新的顶点继续遍历，标记受影响区域。相应证明与可达条件见 MIT 的 Bellman–Ford 讲义。

若图已经是 DAG，则即使有负边，也可按拓扑顺序只松弛一次每个顶点的出边，时间 O(V+E)：所有前驱先处理完成，后来的顶点无需被反复修正。这也把最短路径问题和动态规划中的依赖顺序连了起来。

五、Kahn 拓扑排序：把“全部前置任务完成”变成计数

令 u→v 表示任务 v 依赖任务 u。入度就是还没有满足的前置依赖数。先把入度为 0 的顶点放进 ready 队列；取出 u 后，相当于执行完成 u，将它指向的每个 v 的入度减一。

std::vector<std::size_t> indegree(graph.size(), 0), order;
for (const auto& row : graph)
    for (const auto& edge : row) ++indegree[edge.to];
std::queue<std::size_t> ready;
for (std::size_t u = 0; u < graph.size(); ++u)
    if (indegree[u] == 0) ready.push(u);
while (!ready.empty()) {
    const auto u = ready.front();
    ready.pop();
    order.push_back(u);
    for (const auto& edge : graph[u])
        if (--indegree[edge.to] == 0) ready.push(edge.to);
}
const bool acyclic = order.size() == graph.size();

本例入度为 A=0,B=2,C=1,D=2,E=1,F=0。按字母顺序加入初始队列，再按邻接表顺序更新：

得到 A,F,C,B,D,E。F 没有依赖，也没有被依赖，出现在任意合适位置都可以；拓扑顺序通常不唯一。若要求总是选择当前字典序最小的任务，可以把 ready 改成最小堆，时间会变为 O(E+V log V)。

为什么处理不完就一定有环

每次取出的 u 入度为 0，说明其所有前驱已完成，所以输出顺序满足每条依赖。若还有顶点却没有入度为 0 的顶点，从任一剩余顶点不断找剩余前驱，有限个顶点中一定重复，重复部分构成有向环。

例如加入 E→B 后，完成 A、F、C 就无法继续。B、D、E 互相等待，算法返回失败；这次已输出的前缀不能当作完整拓扑排序。

重复边必须“一次计入、一次扣除”保持一致。自环立即形成环；空图有合法的空顺序。完整程序用 nullopt 表示有环、用持有空 vector 的 optional 表示空图成功。普通队列版本时间 O(V+E)，辅助空间 O(V)。

六、Kruskal：连接全图时，安全地选最便宜的边

现在重新定义问题：把上面各条连接看作无向边，权重是铺设线路的成本。每个地点都要在所属连通分量内连通，要求所有选中边的成本总和最小。

Kruskal 将边从小到大排序。若两端属于不同集合，就选边并合并集合；若已经属于同一集合，就跳过，因为加入它会产生环。

std::sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
    return a.weight < b.weight;
});
DisjointSet sets(vertex_count);
Weight total = 0;
std::vector<UndirectedEdge> selected;
for (const auto& edge : edges) {
    if (!sets.unite(edge.u, edge.v)) continue;
    selected.push_back(edge);
    total = checked_add(total, edge.weight);
}

并查集只需提供 find(u) 和 unite(u,v)。完整程序使用路径压缩和按集合大小合并：find 缩短父指针路径，unite 将小集合挂到大集合的代表上。

F 仍是孤立分量，因此这不是覆盖全部 6 个顶点的一棵树，而是最小生成森林。共有 c=2 个连通分量，选中 V−c=4 条边，总权重为 7。最小生成森林的定义与算法可核对 Princeton Algorithms 的最小生成树章节。

排在前面的便宜边，为什么可以放心选

某条边连接两个当前分量。选一个分量作为割的一边，该边是跨过这个割的最轻候选之一。如果某个最优生成森林没有这条边，加入它会形成一个环；环上必有另一条跨过同一割的边，权重不会更小。

删除那条边后，连通性恢复、总权重不增加，并且包含了本轮选中的边。这种交换说明：每次选择都能扩展到某个最优结果。它与“看见便宜就选”之间，差的是这个安全性证明。

排序 O(E log(E+1))；并查集处理为 O(E α(V)) 摊还时间，加上初始化，总时间 O(V+E log(E+1)+E α(V))。α 是反阿克曼函数，增长极慢。若计入本程序复制并排序的边列表及结果，辅助空间 O(V+E)。

最短路径树和最小生成树，目标不同

三角形 S—X=2, S—Y=3, X—Y=2 足以说明区别。以 S 为起点，最短路径树选 S—X、S—Y，到 Y 的距离为 3，树的总权重为 5。最小生成树选 S—X、X—Y，总权重为 4，但树内从 S 到 Y 要走 4。

一个优化“起点到各点的距离”，另一个优化“全部选中边的权重和”。不能用 MST 给道路导航替代最短路。

Kruskal 允许负权边，因为森林不会靠重复绕环无限降低代价；负自环仍应跳过。重复边和相同权重可能产生多种最优森林，总权重相同。图不连通时不要静默宣称找到 MST，应输出分量数或明确返回森林。

七、把实现结果与另一种方法对照

完整源码将教学机制和验证放在同一个文件，入口运行后自动打印通过结果。

Floyd–Warshall 从“允许哪些中间顶点”的动态规划状态求解，使用 O(V³) 时间；枚举森林为指数时间。它们适合小规模对照，在正式的大图计算中仍应使用符合输入约束的高效算法。

图算法读到这里，可以再与回溯、剪枝和贪心对照：DFS 的深入过程不自动等于枚举所有路径；Dijkstra 和 Kruskal 都采用贪心选择，但安全性的理由不同。需要处理线性序列时，可转到前缀和、双指针与滑动窗口；需要按依赖保存子问题结果时，可继续读动态规划。