简介《图论与网络最优化算法.pdf》是一份面向计算机科学、网络工程及运筹优化学习者的图论算法讲解文档重点聚焦网络最优化问题。内容系统介绍了加权图的最小生成树、Kruskal算法与Prim算法并给出定理证明同时深入剖析割边、割集、割点等关键概念结合定理阐述连通性与可靠网络设计的关系并延伸至匹配等内容有助于读者建立从图论基础到网络优化应用的完整知识链。压缩包内含1个PDF文件大小约1.45MB便于离线阅读。已有222人学习使用适合正在学习数据结构、算法设计与网络优化课程的本科或研究生也适合准备相关面试或竞赛的开发者作为查漏补缺的参考资料。通过这份PDF读者可掌握最小生成树算法的严格证明逻辑理解割点与割集的判定方法并学会将这些理论应用于实际网络拓扑设计和资源分配中。1. 图论与网络最优化从邻接表到最大流的进阶路线很多人把“图论与网络最优化”当成离散数学里的一章考完试就扔。但真到工程里——无论是 CDN 的流量调度、地铁的排班计划、分布式系统里的共识路径还是外卖骑手的取送顺序——你最终都会撞回同一个问题怎么在约束下用尽量少的代价让流量/车辆/请求到达它该去的地方。图论负责把现实关系抽象成点和边网络最优化负责在这些边上算出“最优”的那个方案。本文不打算复述教材而是按一条可上手的路线走先厘清图论建模的基本姿势再写透最短路径与最大流这两类最常被问到的算法最后把“真实网络里图怎么存、参数怎么调、负权边怎么处理”这些落地问题一次性说清楚。适合已经会写代码、但没系统刷过图论优化的人。2. 图论建模与网络流基础为什么邻接矩阵不是首选2.1 图的表达方式决定算法复杂度上限图论的第一步不是选算法而是选存储结构。很多人一上来就用邻接矩阵O(V²)的空间存图在小数据量下没问题但当节点数到 10⁵、边数到 10⁶ 时矩阵连初始化都会超时。工程上常用的有三种方式我按适用场景排个序存储方式空间复杂度查询 u→v 是否存在遍历 u 的所有邻居适用场景邻接矩阵O(V²)O(1)O(V)节点数 2000稠密图邻接表vectorO(VE)O(degree(u))O(degree(u))大多数稀疏图链式前向星数组模拟O(VE)O(degree(u))O(degree(u))竞赛、内存受限、需要按边序号操作// 链式前向星竞赛和底层系统里最常见的图存储 struct Edge { int to, next, w; // to: 目标节点, next: 下一条边的下标, w: 边权 } edge[MAXM]; int head[MAXN], cnt 0; void addEdge(int u, int v, int w) { edge[cnt].to v; edge[cnt].w w; edge[cnt].next head[u]; // 头插法head[u] 存的是 u 的第一条边下标 head[u] cnt; } // 遍历 u 的所有邻居 for (int i head[u]; i ! 0; i edge[i].next) { int v edge[i].to; // 处理边 u-v }这段代码的逻辑在于head[u]是“以 u 为起点的第一条边”的下标edge[i].next指向同一起点的下一条边直到 0 结束。为什么不用vectorint adj[MAXN]因为链式前向星在增删边、反向边操作网络流里要频繁加反向边时不需要动态分配内存cache 命中率也更高。但如果你不是在写竞赛代码而是业务系统直接用邻接表即可可读性更优。空间和时间优化永远为问题服务不要为了炫技牺牲可维护性。2.2 网络最优化问题的统一建模源点、汇点与容量网络最优化里的“网络”不是指互联网而是指有向图加容量约束。正式定义是给定有向图G (V, E)每条边e有非负容量c(e)指定一个源点s和一个汇点t目标是求从s到t的最大可行流量。这里的“流量”必须满足两个约束容量约束每条边上的流量不超过容量和流量守恒除s、t外的每个节点流入等于流出。这个模型能覆盖的问题远比你想象得多。把“节点”换成“任务”“边”换成“依赖关系”容量换成“资源上限”就是一个任务调度问题把“边”换成“城市之间的航线”“容量”换成“座位数”就是航空公司的最大运输量问题。我在实际项目里用网络流解决过一个数据同步问题多个数据源节点要向中心节点同步数据每对节点之间的带宽有限求最大同步吞吐量——本质就是一个最大流。3. 最短路径的三个必调参数从 Dijkstra 到 SPFA 的边界与陷阱3.1 Dijkstra 的完整实现与 priority_queue 的正确姿势Dijkstra 是正权图最短路径的默认选择但它有个容易写错的地方必须用优先队列 懒删除而不是每次遍历找最小节点。后者时间复杂度 O(V²)前者 O((VE)logV)。很多初学者写出的“Dijkstra”在稠密图上跑得比 Floyd 还慢就是吃了这个亏。import heapq def dijkstra(graph, start): graph: 邻接表 {node: [(neighbor, weight), ...]} n len(graph) dist [float(inf)] * n dist[start] 0 pq [(0, start)] # (距离, 节点) while pq: d, u heapq.heappop(pq) if d dist[u]: continue # 懒删除这个条目已经过期了 for v, w in graph[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return dist这里的核心是if d dist[u]: continue它保证每个节点最多被“正式处理”一次但可能被多次推入堆中。空间换时间这是工程上的标准解法。注意Dijkstra 不能处理负权边哪怕只有一条负权边整个算法的贪心基础就崩塌了。那负权场景怎么办看下一节。3.2 SPFA 和 Bellman-Ford负权边的正确打开方式SPFAShortest Path Faster Algorithm是 Bellman-Ford 的队列优化版它允许负权边可以检测负环。但在某些精心构造的图上——比如网格图——SPFA 会退化到 O(VE)比 Bellman-Ford 本身还慢。所以我的建议是只在可能有负权边时用 SPFA且加上节点入队次数上限超过 V 次说明存在负环。from collections import deque def spfa(graph, start): n len(graph) dist [float(inf)] * n in_queue [False] * n count [0] * n # 记录每个节点入队次数用于检测负环 dist[start] 0 q deque([start]) in_queue[start] True while q: u q.popleft() in_queue[u] False for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w if not in_queue[v]: q.append(v) in_queue[v] True count[v] 1 if count[v] n: raise ValueError(存在负环无法求最短路径) return distcount[v]是关键——如果从源点出发能到达一个负环那么环上的节点会被无限次松弛入队次数必然超过节点总数 V。检测到负环后不能继续算最短路径因为路径可以无限小。工程上遇到负环通常意味着数据本身有问题比如依赖关系中存在循环折扣应该抛错出来而不是返回一个没意义的结果。3.3 全源最短路径Floyd 的适用边界与重写技巧Floyd-Warshall 是 O(V³) 的动态规划但它的实现极其简洁适合节点数在 200 以内的场景比如城市的交通网络、微服务调用链的依赖分析。它不需要单独处理负权边只要没有负环这是 Dijkstra 和 SPFA 都不具备的优势。def floyd(dist): dist 是邻接矩阵dist[i][i]0, 无边时inf n len(dist) for k in range(n): for i in range(n): for j in range(n): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist三层循环的顺序不能改——k必须在外层。因为dist[i][j]可能依赖“经过前 k 个中间节点”的dist[i][k]和dist[k][j]如果k在内层这些中间结果还没算出来。这属于“看着对但一跑就错”的经典案例。实际用它时我一般会顺带记录path[i][j] k来还原最短路径的具体走法否则只拿到距离没拿到路径后面回溯还是得重算一遍。4. 最大流到最小费用流从 Dinic 到 SPFA 增广的工程闭环4.1 Dinic 算法为什么 BFS 分层优于直接 DFS 找增广路最大流问题看似直观——不断找从 s 到 t 的路径沿路径推送流量——但朴素 Ford-Fulkerson 在最坏情况下会陷入 O(EF) 的泥潭每次只推 1 单位流量且增广路绕来绕去。Dinic 的解决思路是先用 BFS 给每个节点打上“层级”再用 DFS 只在层级递增的方向上找增广路。这样每次 BFS 后至少有一条最短增广路被阻塞BFS 次数至多 O(V)总复杂度 O(EV²)。struct MaxFlow { struct Edge { int to, next; long long cap; // 剩余容量 } edge[MAXM]; int head[MAXN], level[MAXN], cur[MAXN], cnt 0; void addEdge(int u, int v, long long cap) { addEdgeInner(u, v, cap); addEdgeInner(v, u, 0); // 反向边容量为0用于撤销流量 } void addEdgeInner(int u, int v, long long cap) { edge[cnt].to v; edge[cnt].cap cap; edge[cnt].next head[u]; head[u] cnt; } bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int i head[u]; i ! 0; i edge[i].next) { int v edge[i].to; if (edge[i].cap 0 level[v] -1) { level[v] level[u] 1; if (v t) return true; q.push(v); } } } return false; } long long dfs(int u, int t, long long flow) { if (u t) return flow; for (int i cur[u]; i ! 0; i edge[i].next) { int v edge[i].to; if (edge[i].cap 0 level[v] level[u] 1) { long long f dfs(v, t, min(flow, edge[i].cap)); if (f 0) { edge[i].cap - f; edge[i ^ 1].cap f; // 反向边加上流量 return f; } } } return 0; } long long maxFlow(int s, int t) { long long ans 0; while (bfs(s, t)) { memcpy(cur, head, sizeof(head)); // 当前弧优化 while (true) { long long f dfs(s, t, INF); if (f 0) break; ans f; } } return ans; } };这个实现里有三个参数值得细说。第一edge[i ^ 1]是利用“新增边的序号从 2 开始、反向边是正向边序号异或 1”的位运算特性快速定位反向边——这是把addEdgeInner拆出来的原因保证同一条边的两个方向在数组里相邻。第二cur[u]是“当前弧”优化DFS 时记录每个节点已经试到哪条边了避免重复尝试已经满流的边这一项能把 Dinic 的常数压到很低。第三INF设成长整型最大值因为实际问题里流量可能超过 int 范围比如批发市场的货车运输量按吨计。4.2 最小费用最大流SPFA 增广 反向边的费用修正很多场景不只要“最大流量”还要“在运到最多货的前提下花的运费最少”。把每条边的费用w加上去问题就变成最小费用最大流。常见解法是每次用 SPFA 找到从 s 到 t 的最短路以费用为边权然后沿最短路推送尽可能多的流量直到不存在从 s 到 t 的增广路。struct MinCostMaxFlow { // edge 结构与 MaxFlow 相同额外增加 cost 字段 long long dis[MAXN]; // 费用距离 int pre[MAXN], preEdge[MAXN]; bool inQueue[MAXN]; bool spfa(int s, int t) { memset(dis, 0x3f, sizeof(dis)); memset(inQueue, false, sizeof(inQueue)); queueint q; dis[s] 0; inQueue[s] true; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (int i head[u]; i ! 0; i edge[i].next) { int v edge[i].to; if (edge[i].cap 0 dis[v] dis[u] edge[i].cost) { dis[v] dis[u] edge[i].cost; pre[v] u; preEdge[v] i; if (!inQueue[v]) { q.push(v); inQueue[v] true; } } } } return dis[t] ! INF; } pairlong long, long long minCostMaxFlow(int s, int t) { long long maxFlow 0, minCost 0; while (spfa(s, t)) { long long flow INF; for (int v t; v ! s; v pre[v]) { flow min(flow, edge[preEdge[v]].cap); } for (int v t; v ! s; v pre[v]) { edge[preEdge[v]].cap - flow; edge[preEdge[v] ^ 1].cap flow; minCost flow * edge[preEdge[v]].cost; } maxFlow flow; } return {maxFlow, minCost}; } };pre[v]和preEdge[v]记录的是从 s 到 v 的最短路中的上一个节点和对应边的编号。为什么在这里用 SPFA 而不是 Dijkstra因为反向边的费用是负数——正向边费用为w其反向边费用必须设成-w这样才能在后续增广时“撤销”之前的流量选择。负权边使 Dijkstra 失效SPFA 是标准应对手段。但注意SPFA 的复杂度不稳定密集图上如果超时可以把 SPFA 换成 Dijkstra 势能Johnson 算法用potential[v]把负权边变成非负权。这个优化在大型物流调度里能把耗从几分钟压到几秒。4.3 容量为 0 的反向边为什么每个初学者都会在这里栽一次最大流和费用流代码里最容易出错的不是主算法而是反向边。很多人写完忘了加反向边或者加了但初始容量没设成 0结果跑出来的流量不对还查不出原因。反向边的意义在于当后来找到的增广路需要用到之前已经分配掉的流量时可以通过反向边把流量“退回去”。它不是为了修正 bug而是算法正确性的一部分——Ford-Fulkerson 的增益路径定理要求残余网络中必须包含反向边。调试网络上流问题时我一般先拿一个只有 3 个节点的三角形图试s→a 容量 1a→t 容量 1s→t 容量 1。正确答案是最大流 2。如果只有正向边算法第一次增广 s→a→t 后s→t 的路径就被堵死了——但明明 s→t 还有 1 单位容量可用。加了反向边第二次增广可以走 s→t然后沿反向边 a→s 退回 1 单位整体流量就是 2。如果你写出来的最大流程序只能求出 1先检查反向边。5. 从入门到能的进阶最小费用最大流的稳定推进与负环自检5.1 在有向图上用势能把 SPFA 升级成 Dijkstra当图的规模上到一万节点、五万条边SPFA 的退化会变得很致命。把费用边权用势能h[v]修正成非负权就可以安全使用 Dijkstra 增广。具体做法每次 SPFA 跑完记录h[v] dis[v]费用之后每条边的修正费用为w w h[u] - h[v]它永远非负因为dis[v] dis[u] w移项即得。然后 Dijkstra 在修正费用上跑算出的最短路径在原始费用下仍然最短。// 每次增广前先更新势能再跑 Dijkstra for (int i 1; i n; i) h[i] dis[i]; // dis 是上一次的距离 // 修正后的边权 edge[i].cost h[u] - h[v] // Dijkstra 内部比较时用修正权输出结果时用原始 cost 累加这个技巧在实现时容易犯一个错势能数组要持续累积而不是每次重置。因为每次增广后残余网络的边会变化h[v]必须保持“自上次 SPFA 以来的累积势能”才能保证修正后的权非负。我见过有人在这里把h清零结果 Dijkstra 在负权边上跑出错误结果还不自知。5.2 验证正确性的三个自检测试写完网络流代码不要急着上大样例。按这个顺序自检能在五分钟内定位 90% 的问题第一小数据暴力对拍。写一个暴力 DFS 枚举所有增广路组合节点数 ≤ 10用随机生成的容量矩阵和你的 Dinic/费用流实现对比输出。连续跑 200 组随机样例只要有一组不等立刻调试。这个方法和刷题时对拍的本质一样——你不验证边界边界就会在线上咬你。第二单调性与守恒检查。最大流跑完后检查每个中间节点的流入等于流出除 s、t。最小费用流检查每条边上的流量不超过容量且总费用等于“路径费用 × 路径流量”的累加。网络流代码大多毁在细节——反向边加错、节点编号从 0 开始但从 1 开始初始化、数组开小一格——而这些都会破坏守恒。第三故意造负环。写一个场景三个节点s→a 费用 1a→b 费用 -2b→s 费用 1s→t 容量 100。如果算法陷入死循环或者超过预期增广次数说明负环检测没写好。负环处理的标准姿势是 SPFA 里数入队次数达到节点数就抛异常不要想着“把环走完就能消负”——那是另一套算法最小费用流里的负环取消法工程上你只需要拒绝这种输入。5.3 当“最大”不满足需求把网络流改造成二分图匹配的套路最后给一个实战里高频的思路转换求最大匹配数时不要写匈牙利算法用最大流几句话就能跑出来。把二分图左部每个节点连到源点容量 1右部每个节点连到汇点容量 1左部到右部的可行匹配边容量 1然后跑一遍最大流流量就是最大匹配数。为什么这么做网络流的增广过程本质上和匈牙利算法的增广路径是一致的但网络流有一个额外优势——它能直接处理带权匹配把容量 1 改成需求数量、加上费用跑费用流。适合场景需要把匹配结果扩展成带约束的调度一个人最多接 3 单、某个区域最多派 5 个人时你只需要改容量和费用参数不用重写算法。这个思路是我在日常项目里用图论最优化最多的地方也是面试官最愿意聊的“把经典问题迁移到网络流框架”的切入点。本文还有配套的精品资源点击获取