今天是学习打卡的第53天。按理说我应该把“图论”这个阶段收个尾整理完笔记就切入下一个专题了。但翻热词的时候看到“图论”相关搜索热度一直没下去甚至“图论中图的直径怎么算”“图论与网络最优化算法pdf”“图论及其应用张先迪课后答案”这些长尾问题都涌上来了。我干脆把原计划打乱用这完整的一天把图论里最容易让人卡壳、也最容易被面试官拿来“炒冷饭”的几个点捋了一遍顺便把那些学的时候觉得“这辈子用不上”、后来真在做业务时被反复打脸的内容也重新看了看。这篇文章不是那种把《图论及其应用》从第一章抄到最后一章的知识点汇总那样太无聊了网上随便一搜都是。我这一篇更想解决的是三类人的痛点第一类是刚开始学图论、被各种定理绕晕的初学者第二类是刷LeetCode刷到图就发怵、想建立体系感的选手第三类是工作中偶尔要跟图数据打交道、想快速找回建模感觉的工程师。下面所有内容都是我以自己的踩坑经历、教材使用心得、实际跑代码后的反思为主线写的希望能给你省一点时间。1. 从热搜问题切入图的直径到底怎么算1.1 直径不是“图的对角线”而是最远最短距离先说这个热搜问得最多的“图的直径”。很多人第一反应是“找两个最远的点然后连一条线量长度”这个直觉方向是对的但表述不够严谨。图的直径的定义是图中所有顶点对之间的最短路径长度的最大值。也就是说你先要算出任意两点之间的最短距离然后再从这一堆最短距离里挑出那个最大的值才是直径。举个例子如果有一个简单链状的图顶点是 A-B-C-DA 到 D 的唯一路径长度是 3那这个图的直径就是 3。但如果 A 和 D 之间还多了一条直接相连的边构成一个环状四边形那么 A 到 D 的最短路径就从 3 缩短成了 1整张图的直径也会跟着变成 1。从“唯一路径”到“多了一条捷径”图的直径发生了戏剧性变化。所以算直径时最忌讳的就是看到两个点之间有边就直接用这条边的长度而忽略了其他更短路径的可能性。这里的核心是“最短路径”这四个字。我习惯用一个生活类比来理解它把图想象成一张地铁线路图每个站点是一个顶点线路是边。所谓直径就是这张地铁网里任意两个站点之间最快到达时间的“最大值”。如果一座城市的地铁换乘设计得很糟糕那直径就会很大意味着可能有一段行程要绕特别远反之如果设计得好站点之间很快就能互相到达直径就会很小。这个指标不是用来衡量某一对用户的速度而是衡量整张网络的“最坏情况下的效率”。1.2 三种实用解法与复杂度对比那具体怎么算直径呢针对不同图的规模和边的权重情况我整理了三套思路你按需取用就行方法适用场景时间复杂度实现复杂度逐点 BFS无权图、边数较少的稀疏图O(V × (V E))低只需要会 BFSFloyd-Warshall有权图、顶点数量较少V ≤ 500O(V^3)中三重循环Johnson 算法有权图、稀疏图、含负权边O(V^2 log V VE)高要套 Dijkstra对于小白来说我建议先把第一种吃透。每个顶点做一次 BFS就能得到它到所有其他顶点的最短距离然后把全局最大值找出来。这个方法看着憨憨的但胜在思路直接基本不会写错。如果图的边权都是非负数顶点数几百个以内用 Floyd-Warshall 反而更好写——三重循环先初始化距离矩阵然后不断尝试“经过某个中间点是否能缩短距离”最后扫一遍矩阵取最大值完事。我自己在笔记里存了一个手写的无权图 BFS 算直径的模板Python 大概长这样from collections import deque def graph_diameter(adj): n len(adj) max_dist 0 for start in range(n): dist [-1] * n dist[start] 0 q deque([start]) while q: u q.popleft() for v in adj[u]: if dist[v] -1: dist[v] dist[u] 1 q.append(v) # 更新全局最大距离同时处理非连通图的情况 cur_max max(dist) if cur_max max_dist: max_dist cur_max return max_dist注意如果图是非连通的dist 里会存在 -1这时严格来说直径是无穷大。竞赛里通常会在输入里保证连通性但实际业务图数据可不一定所以我在代码里只对 dist 中非 -1 的值求 max这样就绕开了“非连通导致错误结果”的问题。这个细节教材里不会教实际排查 bug 时却很容易踩。1.3 为什么大家都来搜这个问题热度这么高我猜有几个场景。一是张先迪老师的《图论及其应用》里直径、半径、偏心集这一节是很多院校图论课程的作业题源课后题特别喜欢出“请计算下图中各点的偏心率并找出图的直径和中心”。二是在算法面试中“图的直径”经常被包装成实际问题来考比如“你有一张社交网络关系图消息从一个用户传到邻居需要一轮那全网传播至少需要多少轮”解题思路本质上就是算图的直径。第三个场景也是我自己工作里真实遇到的在设计一个分布式缓存系统时为了估算多级缓存之间的数据同步延迟上限我把缓存节点之间的网络延迟抽象成一张加权图算出的直径就是最坏情况同步延迟。这种“最坏情况上限”的思维在系统设计里其实非常值钱。2. 学图论不能只盯着算法看先理清这几条主线2.1 图的存储结构邻接矩阵还是邻接表很多新手一上来就背算法模板结果连图怎么存储都没想明白写出的代码不是内存超限就是遍历顺序混乱。我建议在动手前先把这三个最基础的问题想清楚顶点和边分别代表什么边有没有方向边上有没有权重。想清楚之后存储方式就很好选了。邻接矩阵用一个 V×V 的二维数组存边权优点是判断两个顶点之间是否有边是 O(1) 的Floyd 算法用起来尤其顺手。缺点是空间是 O(V^2)V 超过一万就非常吃力。邻接表每个顶点挂一个链表或数组只存与它直接相连的邻居。优点是省空间BFS/DFS 遍历时开销也小绝大多数竞赛题和面试题推荐用这种。缺点是判断“u 和 v 是否相邻”需要遍历一遍列表但实际场景中这个操作频率并不高。链式前向星说实话如果不是在打 ACM 或者跑超大规模图我建议普通学习者先别碰。它确实快但抽象程度太高容易劝退。我的个人习惯是刷题为主就无脑邻接表涉及 Floyd 或稠密图就邻接矩阵。工程里如果用的是 Python我经常会直接借助邻接表加一个字典来存边权比如adj[u].append((v, weight))兼容性很强。2.2 树的特化性质是你理解图论的捷径树是图的一个特例但正因为特化它有一堆好用得惊人的性质。我当时记第一个性质时特别有印象一棵有 n 个顶点的树恰好有 n-1 条边。你拿这个性质去判断一个图是不是树一句话的事。反过来如果一个连通图有 n 个顶点和 n-1 条边那它就是树不可能有环。第二个性质是树里任意两个顶点之间有且仅有一条简单路径。这意味着在很多问题里树结构可以把“找路径”从复杂的搜索问题降维成“找最近公共祖先”的问题。我在刷二叉树题目时积累的手感放大到更一般的树结构上一样适用。然后是生成树问题Kruskal 和 Prim 两种贪心算法前者适合边少图稀疏图按边权从小到大排序然后用并查集判断是否成环后者适合点少但边特别多的稠密图。实际选举哪种不用背你只要记住一句话稀疏图用 Kruskal稠密图用 Prim。我学的时候走了弯路总是强迫自己两个模板都默写一遍后来才意识到先用数据规模判断再选算法才是最高效的。2.3 二分图、连通分量与强连通分量构成了图论的判断家族在刷题和面试里“给你一张图问一些性质”这一类问题其实翻来覆去就考这么几样是不是二分图用染色法从一个点开始 BFS/DFS给相邻点染相反颜色如果出现冲突说明不是二分图。二分图最经典的应用就是匹配问题比如“给 N 名员工分配 M 个岗位每个员工能胜任若干岗位如何让尽可能多的员工都上岗”建模成二分图最大匹配就行。有几个连通分量无向图里从任意未访问顶点开始 DFS一次遍历能覆盖到的就是同一个连通分量。社交软件里的“你可能认识的人”推荐、后端服务里“不同网络区域是否可达”的判断背后都是连通分量思想。有向图里的强连通分量最常用的是 Tarjan 算法。它把所有互相可达的顶点缩成一个点最终形成一张有向无环图DAG。一旦图变成了 DAG你就能用拓扑排序处理问题比如“哪些模块必须先编译”“哪些服务之间没有循环依赖”。这里我想多说一句很多工程师对 Tarjan 有畏难情绪但它真的不难核心是维护一个栈和一个时间戳数组理解递归回溯时的栈帧变化再配合一到两个例子手推一遍就通了。这类算法第一次学的时候慢一点完全没关系关键是搞懂原理而不是背模板。3. 教材搭配方案张先迪、网络最优化算法资料如何配合使用3.1 张先迪《图论及其应用》该怎么读才不会被证明劝退这本书名气很大很多学校直接拿它当教材。但我观察到一个普遍现象初学者翻开第一章看到“图、简单图、多重图”等概念还好再看到后面各种定理的严格证明就受不了了。我的意见是这本书更适合当案头工具书而不是从头到尾的“刷书”对象。第一遍学习时你把基本概念、握手定理、树的性质、连通性、图的矩阵表示这些章节认真过一遍就好到了匹配理论、Ramsey 定理这种偏理论深度的章节可以先看懂定理表述和结论证明过程留到需要深挖时再回来啃。很多人搜“图论及其应用张先迪课后答案”我的建议是先自己推导实在卡住再看答案。图论题的答案经常是“点睛之笔”比如构造法证明题里那一个巧妙的构造看答案前想三天看答案后恍然大悟。但如果你永远直接看答案你永远培养不出“自己构造”的脑回路。我在打卡的第 47 天就是纯靠自己画图推了一个关于树的重心的性质的题推了一个多小时虽然过程磕磕绊绊但效果远好于直接抄答案。这一点我很确定。3.2 用《图论与网络最优化算法》补齐应用视角如果只读张先迪那本书你会觉得图论是一门偏数学的学科。但加上网络最优化算法的资料后整个视角就变了。像最短路、最大流、最小费用最大流、最小生成树这些“能立刻用代码跑出结果”的算法才是图论在工程和竞赛中发光的核心。我用的是电子版 PDF它的章节安排里网络流、匹配、整数规划等内容都给出了算法步骤和实例和教材的证明形成互补。我的阅读顺序是先看最短路再看生成树然后再啃最大流。最大流这块很多人第一次学会有点懵我建议一定要亲手画一遍残量网络。你真去画了就会发现增广路其实就是“从源点到汇点还能找到一条容量为正的路径”的过程。这种从抽象到具体的转化光靠看 PDF 是不行的必须配合动笔。3.3 一天的时间线我 Day53 是怎么安排的为了给也同样在坚持打卡的朋友一个参考我把这一天的学习安排列出来上午大约 2.5 小时集中看张先迪教材中直径、半径、中心相关的章节同时把邻接矩阵、邻接表两种存储方式的手写实现都过了一遍因为后面所有算法都建立在存储之上。下午大约 3 小时打开平时刷题的网站完成三道图论题。一道是“求无权图的直径”我故意不用 networkx 里现成的diameter()函数而是自己 BFS 实现了一遍这样理解才足够深。第二道是“判断二分图”用染色法手写。第三道是“最小生成树”用 Kruskal 并查集实现。晚上大约 2 小时把今天犯的错、之前的疑惑统一整理成一篇笔记。比如我发现自己在 Floyd 算法里经常会漏掉“中间顶点 k 必须放在最外层循环”这个细节就在笔记里用红字标注并配了一个错误例子说明为什么内层循环不行。说句实话一天 7 小时左右的状态对我来说是常态但并不是每天都能保持。如果你时间有限你可以把上午压缩到 1 小时重点看看定义和例题晚上再抽半小时做题效果也不会差太多。学习图论这种知识密度高的主题短时间高强度的“沉浸式”学习比每天只摸十分钟要高效得多。4. 几个无论如何都应该亲手写一遍的图算法4.1 BFS 和 DFS是所有图算法的地基BFS 和 DFS 看似简单但很多复杂算法都是从它们衍生出来的。BFS 的特点是逐层向外扩展天然自带“最短路径”属性所以无权图的最短路用它算最简单。DFS 的特点是沿着一条分支走到底特别适合检测环、计算连通块、处理回溯类问题。我写过一个很典型的 BFS 求无权图最短路径的模板差不多是下面这样from collections import deque def bfs_shortest_path(adj, start, target): n len(adj) dist [-1] * n dist[start] 0 q deque([start]) while q: u q.popleft() if u target: return dist[u] for v in adj[u]: if dist[v] -1: dist[v] dist[u] 1 q.append(v) return -1 # 不可达这个模板在刷题时几乎可以直接套用到“单词接龙”“打开转盘锁”这类问题上换汤不换药。你要注意的是dist数组同时起到了“访问标记”和“记录步数”的双重作用省掉单独开一个 visited 数组的开销。这种小优化写多了就变成习惯代码也会清爽很多。4.2 最短路径三兄弟Dijkstra、Bellman-Ford、Floyd这三兄弟我每次讲到都忍不住提醒一句千万别把它们的适用范围搞混了。Dijkstra处理边权非负的单源最短路贪心思想 优先队列优化后是 O((VE) log V)是面试和竞赛中的主力。为什么它不能处理负权边因为 Dijkstra 每次贪心取出当前距离最小的点并认为这个点的距离已经确定不再更新。一旦有负权边存在可能出现“某个点被标记为已确定后后来通过一条负权边变得更短”的反例贪心前提就崩了。这个例子我建议你自己画一个只有亲手推一遍才会真正信服。Bellman-Ford可以处理负权边还能检测负权环。思路是“对所有边松弛 V-1 轮每轮至少有一条最短路径的边数加 1”。效率不咋地但胜在鲁棒。SPFA 是它的队列优化版大部分情况下跑得快但在最坏情况下复杂度可以退化所以竞赛里如果出题人想卡你SPFA 是可能被卡掉的。Floyd全源最短路代码短、思路直白三重循环完事但复杂度 O(V^3)。如果顶点数量在 500 以内完全可以直接用它不用折腾 Johnson 算法。我在写代码时有一个习惯只要问题里没有明确说“边权有负数”我就默认用 Dijkstra因为它在正权图上表现最稳定。只有出现负权边我才切换到 Bellman-Ford。4.3 网络流从最大流到二分图最大匹配的建模思路网络流这一块其实是图论里特别迷人的部分。最大流的核心就是 Ford-Fulkerson 方法不断在残量网络里找增广路直到找不到为止。E-K 算法就是 BFS 找最短增广路Dinic 算法通过分层图实现多路增广效率更高。面试里考网络流的不多但竞赛里很常见而且最大流有一个特别漂亮的建模技巧二分图最大匹配可以转化为最大流问题。具体做法是源点连向左部所有顶点容量为 1左部顶点连向右部可匹配的顶点容量为 1右部顶点连向汇点容量为 1。在这个网络上跑一遍最大流最大流的值就是最大匹配数。我第一次看到这个转化时真的被惊艳到了原来“人和岗位的匹配”这种问题居然能用水流来模拟。如果不想引入太复杂的网络流模板二分图匹配也可以用匈牙利算法代码短很多思路是“让出一个位置给新来的人自己再去找别的”的回溯逻辑学有余力的可以两个都掌握。5. 把图论落到真实场景建模往往比会背算法更值钱5.1 地图导航与网络路由里的图论地图导航是图论最朴素的应用场景。地图上的路口是顶点道路是边红绿灯、限速等条件折合成边权导航就是从起点到终点的最短路径问题。很多人以为导航用的是 Dijkstra但实际上更常见的是 A* 算法。A* 在 Dijkstra 的基础上引入了一个启发式函数比如直线距离或估算时间让搜索方向更快朝着终点靠拢从而减少无效搜索。这背后的思想其实很简单如果我们知道终点大致在哪个方向就没必要把整张地图都展开。图的直径在导航场景下的意义也很有意思。你算出一张城市路网的直径就相当于知道“这座城市从一头到另一头最坏需要多久”。这个数值在服务端有实际用途比如做限流或超时配置时如果城市级路网的上限时间已知那么给用户端的请求超时时间至少要大于这个直径否则就会误杀合法的长行程请求。类似思路在 CDN 缓存系统里也成立。5.2 社交网络分析与推荐系统里的中心性在做社交网络分析时图论的中心性指标比“图的直径”这个名字要常用得多。度中心性看的是这个点跟多少人直接相连直观但容易偏向“广撒网”的节点。紧密中心性看的是该点到其他所有点的平均最短距离越小的点越在“信息传播的中心”。介数中心性看的是有多少条最短路径经过了该点它最能反映“关键枢纽”角色但计算量也最大。有意思的是图的直径在这些指标计算中扮演了一个“边界角色”图的直径越大信息要传到全网需要经过的轮数上限就越大这直接影响传播模型的调参。比如迅雷下载中的节点发现、P2P 网络中的广播扩散都要考虑“网络直径带来的延迟上限”。如果你是在大厂做社交推荐这些概念大概率会以某种形式出现在需求讨论中早学早受益。5.3 依赖编排与 DAG图论给工程世界最重要的礼物我个人认为工程实践里最有价值的图结构是 DAG也就是有向无环图。编译系统在编译前需要知道每个源文件依赖哪些头文件这就是一个 DAG持续集成流水线里任务 A 完成后才能跑任务 B这又是一个 DAG甚至你早上起床后的“做早餐”步骤煮咖啡、热牛奶、烤面包也可以画成一个 DAG。处理 DAG 的经典算法是拓扑排序输出的顶点顺序满足“所有边都从前往后”。如果你发现拓扑排序无法覆盖全部顶点那说明图中存在环可能意味着某个依赖链出现了循环引用。我在实际工程排查中就用过一次一个微服务依赖关系图里A 依赖 B、B 依赖 C、C 又反向依赖 A导致线上启动时服务一直互相等待。当时用拓扑排序检测出这个环之后问题立刻定位了。这种“图论直接救项目”的成就感远比刷题时 AC 三道题来得强烈。6. 写在第 53 天结束前的话如果你也在坚持每日打卡稍微有一点自己的小体会想分享图论这门课最忌讳的是“看得多、写得少”。图论的算法和数据结构不同它极度依赖直觉和动手能力很多题你看答案觉得“啊原来如此”但自己独立写的时候完全不知从何下手。我的解决办法是每学一个新算法就必须在纸上画至少一个例子再手写一遍不查模板的代码。这个过程很慢但很值。还有一个具体的小建议把图论的笔记按“问题类型”而不是“算法名称”来组织。比如“如何判断两点是否连通”下面不只写 DFS/BFS 的模板还要写并查集的做法在“如何找环”下面既写 DFS 的遍历标记法也写拓扑排序检查剩余节点的方法。这样当你遇到一个新题时你不是翻开书找算法而是先判断这个问题属于哪一类再选择顺手的方法。这种思维方式我认为是这个主题带我走向“内化”的关键一步。最后如果你学到这里不妨用下面三个问题自测一下第一给定一个含 4 个顶点的环你能算出它的直径是多少吗第二一张有 6 个顶点的连通图边数最少是几条最多是多少第三用 BFS 实现一个“判断二分图”的函数你能在五分钟内写出来吗如果都能答上来说明你这一天的图论学得很扎实。如果你之前被图论的证明劝退过不妨换个思路先从“为了解决问题而学算法”出发再回头看书里的定理你会发现以前觉得难的东西突然就变得能看懂了。