图论与路径

本页按场景选择方法；通过各条目链接阅读完整推演、源码和输出。

约定顶点编号为 0 到 V-1，所有邻接下标和起点均须合法；矩阵表示要求方形。每个 package main 是独立文件/模块（Go 1.22+），不能合并重复 Edge。距离、路径费用与容量计算均要求中间结果可用 int 表示，inf 不能与合法距离混淆；本轮输出仅经静态推导，未执行。

要解决的问题	可选方法	选择前确认
遍历可达节点或划分无向图连通分量	DFS、BFS、连通分量	BFS 的首次到达只在无权图表示最短步数；深图递归需关注栈深度。
安排依赖顺序、检测有向环或分成两组	拓扑排序、三色 DFS、二分图判定	拓扑排序仅对 DAG 输出全部节点；二分图染色与依赖排序解决不同约束。
从一个起点求非负边权最短路	Dijkstra	示例扫描实现为 O(V²+E)；大型稀疏图可用堆降低选点成本。
路径可能含负边	Bellman–Ford	时间 O(VE)，可检测从起点可达的负权环。
小图需要频繁查询所有点对距离	Floyd–Warshall	时间 O(V³)；不可达值与距离相加须避免溢出。
以最低总成本连接顶点	Kruskal或Prim	Kruskal 排序边并用并查集判环；Prim 示例用矩阵，时间 O(V²)，图不连通时无单棵生成树。
边有容量限制，需要最大总传输量	最大流与残量网络	Edmonds–Karp 示例用 BFS 寻找增广路，并会修改传入容量矩阵。

遍历可达节点与划分连通分量

广度优先搜索

正文、推演与完整示例：广度优先搜索。

边有不同权重时首次到达不一定最优，应使用合适的带权最短路算法。

深度优先搜索

正文、推演与完整示例：深度优先搜索。

从起点递归访问尚未见过的邻居，seen 防止在环中重复进入节点。它能用于可达性、连通分量和回溯搜索。 遍历时间 O(V+E)。

每个顶点和边至多处理常数次；极深图可改用显式栈避免递归栈过深。

连通分量

正文、推演与完整示例：连通分量。

在无向图里，从一个未访问节点出发能到达的所有节点构成一个连通分量。对每个剩余起点重复搜索即可得到完整划分。 总时间 O(V+E)。

示例用栈迭代并在入栈时标记，避免同一节点被多次加入。

检查依赖顺序、环与二分分组约束

拓扑排序

正文、推演与完整示例：拓扑排序。

先统计每个节点的入度，把所有入度为零的节点放入队列。移除节点时减少其后继的入度，新变成零的节点即可入队。 仅有向无环图能输出全部节点。

若结果数量小于顶点数，剩余节点属于有向环或依赖于环，无法给出完整顺序。

有向图环检测

正文、推演与完整示例：有向图环检测。

指向已经完成的节点并不构成当前路径上的环，这正是普通 visited 标记不够用的原因。

二分图判定

正文、推演与完整示例：二分图判定。

二分图要求每条边的两端染成不同颜色；若相邻两点被迫同色，就不能二分。奇数长度环会造成这一冲突。

按边权和查询范围求最短路

Dijkstra 最短路

正文、推演与完整示例：Dijkstra 最短路。

示例使用简单的 O(V²+E) 扫描；大型稀疏图可用堆降低选点成本。

Bellman–Ford 最短路

正文、推演与完整示例：Bellman–Ford 最短路。

一轮松弛允许最短路径多经过一条边，因此最多 V−1 轮足以覆盖无环最短路径。再扫描一次若仍能改进，说明存在从起点可达的负权环。

算法允许负边，但时间 O(VE)，通常比 Dijkstra 慢。

Floyd–Warshall 最短路

正文、推演与完整示例：Floyd–Warshall 最短路。

第 k 轮只允许前 k 个节点作为中转点，用 i→k→j 与现有 i→j 距离取较小值。三重循环得到所有点对的最短距离，适合顶点数较少且查询很多的图。 时间 O(V³)。

需要用足够大的 inf 表示不可达，并避免相加溢出。

用最低边权总和连接全部顶点

Kruskal 最小生成树

正文、推演与完整示例：Kruskal 最小生成树。

图不连通时无法得到单棵生成树，示例返回 −1。

Prim 最小生成树

正文、推演与完整示例：Prim 最小生成树。

本例 Prim 最小生成树使用 inf = int(^uint(0) >> 1) 作为本机 int 的最大值哨兵，避免固定 1<<60 在32位目标上不可表示。矩阵中的 -1 表示没有边；合法边权和总成本必须在 int 范围内且不与 inf 混淆。若当前最小候选仍为 inf，说明余下顶点不连通，返回 -1。

示例用方形对称矩阵与 O(V²) 扫描；-1 表示没有边，只接受非负边权，边权及总和须小于 int 上限。一般最小生成树可含负边，但本例用负数作哨兵，不能直接用于该情形。稀疏图通常用优先队列和邻接表。

在容量限制下增加网络流量

最大流基础

正文、推演与完整示例：最大流基础。

残量网络记录一条边还能增加多少流，也记录沿反向边撤回已有流的能力。BFS 找到一条增广路后，取路上的最小剩余容量作为本次增量，并同步更新正反边。 本例使用 Edmonds–Karp 算法。

反复执行到找不到路径即得到最大流；示例会修改传入的容量矩阵。前提是方形非负容量矩阵、合法且不同的源点 s 和汇点 t，容量累加不超过 int；s == t 不属于本例契约，否则增广循环无法前进。

静态自检

预测两点有向环 0→1→0 的拓扑排序结果。再说明为何不能将 BFS 的首次到达套用于带权图。提示：先计算入度。

参考解法

两个入度都为 1，初始队列为空，返回空序列；数量小于 V 表示无完整拓扑序。带权路径可能经过更多边却总成本更低，应按边权前提选择最短路算法。