图论这门课，我在大学的时候学得晕晕乎乎，课本上的定理一个接一个，总觉得它就是一堆“点和线”的抽象游戏。直到工作以后，在一次业务改造里被图狠狠地救了一回，我才真正意识到：图论不是数学课的专利，它就是一套用来描述“关系和连接”的通用语言。后来我把当年的笔记、课堂讲解和实际项目经验重新整理了一遍，就成了这套“课堂图论合集”的底子。
这套内容适合谁？我觉得覆盖面比想象中广。如果你是刚接触数据结构的大学生，正在为期末考试和考研复习发愁；如果你是算法竞赛选手，想系统梳理一下图论的常考模型；又或者你是个工程师，手上正遇到路由规划、任务编排、社交推荐这类问题——这篇内容都能给你一个从0到1的框架，以及一些课本上不会写、但实战里一定会踩的坑。
先说清楚一个前提：我不会把图论的所有定理铺开讲，那样没人能消化。我更想做的，是帮你看清图论里最关键的那根主线——怎么把问题变成图，怎么在图上做计算，以及为什么有些算法好用、有些算法看着简单却不能用。
1. 先弄明白：图到底是什么，别被“图”字带偏
1.1 从地铁线路图开始认识图的本质
很多人第一次接触图论，脑子里蹦出来的是函数图像、柱状图、折线图，然后就开始犯迷糊：图和图之间怎么还有这么大学问？这里的“图”，指的是由顶点和边组成的结构。
最简单的例子就是地铁线路图。你打开任何一张地铁图，能看到一个个站名，还有连接站名的线路。站名就是顶点，线路就是边。你要从“人民广场”到“世纪大道”，本质上就是在问：从某个顶点出发，沿着边能不能到达另一个顶点，走哪条路最省时间。这和函数图像完全不是一回事。
我上课的时候特别喜欢让学生做一件事：把你所在城市的地铁图简化成点和线，然后用纸笔画出来。一旦你亲手画过，就会自然理解图的核心抽象思路——我们只关心“谁和谁相连”，不关心这两个站在地图上的实际地理位置。地铁图里的距离是扭曲的，但连接关系是真实的，这就是图的力量：它能把真实世界里杂乱的信息，压缩成最纯粹的关系结构。
1.2 三组必须一开始就分清的图结构
图论之所以入门容易晕，主要是因为它有几组“双胞胎”概念，长得像，性质完全不同。第一组是有向图和无向图。无向图的边没有方向，比如朋友关系，你认识我，我就认识你；有向图的边有方向，比如微博的关注关系，我关注你，不等于你关注我。工程里很多错误都出在方向没想清楚。
第二组是带权图和无权图。无权图只关心“有没有路”，带权图给每条边附加了一个数值，这个数值可以是距离、时间、成本、容量。地图导航就是典型的带权图，边上的权就是路程或耗时；而一个纯社交关系网常被当作无权图，因为你知道两个人认识与否就够了，不需要给友谊打分。
第三组是连通和非连通。一个图里，任意两个顶点之间都存在路径，这个图就是连通的；否则就是非连通的，会分裂成好几个互不连通的区域。这部分概念经常和“连通分量”“强连通分量”绑在一起出现，也是后面很多算法讨论的前提。
1.3 图的“度”其实藏着很多信息
每个顶点的度，就是指它连了多少条边。无向图里一个顶点的度就是邻居数量；有向图还要区分入度和出度——入度是“指向我”的边数，出度是“从我出发”的边数。
别小看这个概念。在社交网络里，一个人的粉丝数就是入度，关注数就是出度；在网页排名算法里，一个页面被多少其他页面链接，同样是入度的应用。我第一次意识到“度”这么有信息量，是在做网络故障排查的时候：一个节点忽然间大量出错，其他指标都正常，后来发现是某个入度极小的上游节点挂了，所有流量像漏斗一样集中到了它身上。图论里对度的分析，放到运维场景里就是最基础的依赖分析手段。
还有一条经典的握手引理：一个无向图里所有顶点的度之和，等于边数的两倍。这个引理简单到像废话，但考试和实战里都有大用——比如判断一组度序列是否可能构成一个图，或者快速估算一张图的边数规模。
2. 把现实问题翻译成图：建模这一步决定了后面的一切
2.1 建模的本质是选择“顶点”和“边”
学图论最大的坎不是算法，而是建模。很多人看完最短路径算法，转头遇到一个实际问题，还是不知道该怎么套。原因很简单——他不知道把什么当成顶点，把什么当成边。
我后来总结出一个特别朴素的方法：先看你手里有哪些“实体”，再想实体之间有哪些“关系”。实体是顶点，关系是边。比如外卖派单问题，商家、骑手、顾客是顶点，它们之间的可达路线是边；再比如数据库表之间的外键关联，表是顶点，外键关系是边。
有一道经典的建模题是“过河问题”：农夫要带狼、羊、白菜过河，船只能装农夫加一个东西，狼不能和羊单独相处，羊不能和白菜单独相处。看起来和图论八竿子打不着，但其实可以把“岸边状态”定义为顶点，比如左岸有农夫、狼、羊，右岸有白菜，是这个状态；每个合法的划船动作就是一条边。求最少过河次数，就变成在状态图上求最短路径。这道题我第一次看的时候拍案叫绝，它彻底打开了我的思路——图论的顶点可以不是物理实体，而是一个“状态”。
2.2 存储方案选型：邻接矩阵还是邻接表
建模完成之后，下一个问题是如何把图存进程序里。最常用的两种方式，邻接矩阵和邻接表，各有各的适用场景。
邻接矩阵就是一个二维数组，g[i][j]表示顶点 i 到顶点 j 是否有边（或者边的权重）。它的优点显而易见：判断两个顶点是否相连，O(1) 时间就能搞定；写代码也最直观。缺点更明显，空间复杂度是 O(V²)，V 是顶点数。1万个顶点的图，矩阵就要存1亿个格子，直接爆内存。所以邻接矩阵适合稠密图——边比较多，接近 V² 量级的图。
邻接表则是一个数组，数组每个下标对应一个顶点，后面跟一个链表或动态数组，里面存它所有的邻居。空间复杂度只有 O(V+E)，E 是边数。在稀疏图里，也就是实际工程里大多数图，这是碾压级的选择。1万个顶点、5万条边的图，邻接表轻轻松松存下。
如果你用 C++，可以拿 vector adj[N] 来存；用 Python 可以拿 dict 或 defaultdict(list) 来构建。我自己的习惯是：做题和写原型，先用邻接表；只有当需求明确需要频繁查询“任意两点是否相邻”，而且顶点数在几千以内，才考虑邻接矩阵。别小看这个选择，选错了，后面所有算法都会一起遭殃，因为复杂度全建立在图的存储形式上。
2.3 一次真实的建模：课程排课与拓扑排序
我的一个学生曾经在培训机构做教务系统，他们最头疼的问题之一是排课。课程之间有先修关系，比如“离散数学”必须先修“高等数学”，“算法设计”必须先修“数据结构”。教务老师手工排课时经常排出一个死循环——A课程要求先修B，B又要求先修A，课程根本排不出来。
这就是一个典型的图模型：每门课是一个顶点，先修关系是一条有向边，从先修课指向后续课。整个排课过程，就是在有向图里做拓扑排序——找出一个线性的顺序，使得每条边的起点都在终点前面。
拓扑排序的方法很直观，我习惯用 Kahn 算法：先统计每个顶点的入度，把所有入度为0的顶点放进队列（这些课没有任何先修课，可以立刻开设），然后不断出队，每出一个顶点，就把它指向的所有邻居的入度减1，如果有邻居入度变成0，就加入队列。最后如果出的顶点总数小于总顶点数，说明图里有环，也就是课程之间有循环依赖。
我第一次带他跑通这个流程时，他特别感慨，说排课排了三年，终于知道为什么有时候课程无论怎么排都会冲突——不是排课的人粗心，而是这个图结构本来就有环。这件事让我意识到，图论不是拿来考试用的，它真的能改变一个人处理日常复杂系统的方式。
2.4 用图论语言重写常见业务问题
建模能力是可以刻意练习的。我自己的方法是：遇到任何带有“关系”“依赖”“网络”“最优路径”字眼的问题，先逼着自己用图论的术语重新描述一遍。
比如“公司部门之间要传递文件，怎样最少跳转能让所有人都收到消息”，翻译成图论就是“在无向图里找一个起点，做 BFS，记录最大层数”——本质上是广度优先遍历，甚至和图的直径有关联。又比如“城市里要铺设光纤，把几个机房全部连起来，总成本最低”，翻译成图论就是“求最小生成树”。再比如“用户A和用户B之间有哪些共同好友”，翻译成图论就是“求两个顶点之间长度为2的公共路径端点”。
当你主动做这个翻译练习一段时间后，会发现大多数所谓的“新业务问题”，底层都是图论里几十年前就研究过的老问题。你不是在创造新算法，你是在把经典算法用到新场景里。
3. “图上两点有多远”：从最短路径到图的直径
3.1 直径的定义：先找最短路，再取最大值
热搜词里有“图论中图的直径怎么算”，说明这是个高频疑问。图的直径，定义非常容易说清楚：图中任意两个顶点之间最短路径长度的最大值，记作 diam(G)。注意是“最短路径长度”的最大值，不是“最长路径”——这两个东西天差地别。
我见过太多人在这里翻车：拿着“直径”两个字，以为是求图上距离最远的那条路，结果用 DFS 去搜最长路径，搜到天荒地老。求最长路径是个极其困难的问题，在一般图里属于 NP-hard，顶点稍微多一点就跑不动；而直径是可以在多项式时间内算出来的，因为它的本质是“所有点对最短路径”的最大值。
打个比方：如果你把整个图想象成一张蜘蛛网，直径不是网上最长的那根丝线，而是“从任意一只蜘蛛出发，爬到另一只蜘蛛那里最少需要走几步”这个数字里最大的那个。它衡量的是整张网最远的两个点之间，至少需要几跳才能相遇。
3.2 无权图的直径：两轮 BFS 就够了
如果图是无权图，每条边的长度都算1，那么计算直径有个非常经典且高效的方法：任选一个起点，做一次 BFS，找到离它最远的顶点 u；再从 u 出发，做一次 BFS，找到离 u 最远的顶点 v，u 和 v 之间的距离，就是整棵树的直径。
注意，我说的是“树”，而且这个结论的前提是图本身是一棵树。两轮 BFS 求直径的结论严格来说适用于树这种特殊图，对一般无向图并不总是成立。这一点必须说清楚，不然照搬就会出错。
那一般无向无权图的直径怎么求？最稳妥的办法是跑 Floyd-Warshall 或者对每个顶点分别做 BFS。因为 BFS 可以求出单源点到其他所有点的最短路，所以从每个顶点分别做一次 BFS，时间复杂度是 O(V(V+E))，在顶点数几千的规模下完全可行。记录下所有点对最短距离的最大值，那就是直径。如果图是非连通的，顶点之间没有路径，直径通常定义为无穷大，或者你只关心每个连通分量内部的直径——具体看需求怎么定。
3.3 带权图的直径：Floyd 与 Dijkstra 的选择
一旦边带上了权重，问题就复杂一点。带权图的直径同样是“任意两点最短路径长度的最大值”，但这时候“最短路径长度”要用带权最短路算法来算。
当图比较小（比如顶点数在几百以内），Floyd-Warshall 是最简单的方案：三重循环，每次尝试用中间顶点 k 来松弛 i 到 j 的距离，最后 dist 矩阵里直接存下所有点对最短路。它的时间复杂度是 O(V³)，代码极其简单，面试和考试里经常用来快速拿结果。我第一次手写 Floyd 时没想到这东西这么短，十来行就搞定，缺点是只能对付小图，2000个顶点的立方运算已经超过80亿次，程序会明显卡顿。
当图的规模变大，就要用 Dijkstra 做主力的单源最短路，然后对每个顶点轮流跑一次。堆优化的 Dijkstra 单次复杂度是 O((V+E)logV)，跑 V 次就是 O(V(V+E)logV)。在边数不多、顶点数上万、边权非负的情况下，这是更现实的选择。注意 Dijkstra 要求边权非负，如果图里有负权边，就要用 Bellman-Ford 或者 SPFA，没有"免费的午餐"。
3.4 直径为什么容易和“最长路径”混淆
网上特别多人把图的直径理解成“最长路”或者“关键路径”，这是需要掰开揉碎讲清楚的地方。
“最长路径”在一般图里为什么难？因为路径不允许重复经过顶点，你要判断一条路径是不是最长的，本身就涉及指数级搜索，这跟“是否存在一条哈密顿路径”是同一个难度级别的问题，目前没有多项式算法。而直径是每对点最短路的最大值，最短路本身是好求的，所以直径好算。
但工程里确实有很多场景需要“找一条尽可能长的简单路径”，比如排工序、算项目关键链路。这不是求直径，而是求最长路，解决办法不是在图论里硬搜，而是先判断图是否是有向无环图（DAG）。如果是 DAG，最长路径可以用拓扑排序配合动态规划在 O(V+E) 时间内解决；如果图里有环，问题就难了。我自己的经验是，当业务方说“求最长链路”时，我会先确认有没有环，没有环就放心大胆地 DP，有环就得先做环检测、把环处理掉。
4. 那些“看起来高级”的图算法，其实都在解决现实里常见的三类问题
4.1 连通与分组：并查集和连通分量
很多工程场景需要反复回答“这两个节点在不在同一个集合里”，比如社交网络里的好友分组、联通网络里的设备分区、数据库里的集群状态判断。如果每次都从图上做一次搜索，代价太高；这时候并查集是最顺手的数据结构。
并查集维护的是一堆集合，它特别适合动态添加边、随时询问两个顶点是否连通的问题。我习惯用路径压缩加按秩合并的写法，这两项优化加起来，单次操作几乎可以认为是常数时间。考试和竞赛里，Kruskal 最小生成树算法也要用并查集配合实现，所以这个结构基本是图论入门的“免费技能”。
我有一次处理一个线上故障，服务之间有调用链依赖，需要快速判断某个根因节点挂了是否会影响到特定服务。我先用调用链数据建图，做一次连通分量划分，每个分量里的节点挂了一个分组的 ID，之后每次排查就只需要查分组 ID 而不需要重新遍历图。这种“预处理 + 查询”的思路，比每次临时搜索省一个数量级的时间。
4.2 最小成本连接：最小生成树
最小生成树解决的问题很朴素：把 n 个顶点连通起来，同时让边权之和最小。它对应的现实场景包括网络布线、管道铺设、集群组网。算法有两个经典选择：Prim 和 Kruskal。
Prim 适合稠密图，从某个顶点出发，每次加一条“连接当前树外顶点且权最小”的边，用优先队列可以把复杂度降到 O((V+E)logV)。Kruskal 适合稀疏图，做法是把所有边按权重排序，从小到大逐条尝试，如果边的两端已经在同一个连通分量里就跳过，否则用并查集合并，复杂度是 O(ElogE)。
说实话，在我自己的工作里，用到最小生成树的机会比最短路少很多，但它依然是图论应用里不可绕过的一块。特别是当你遇到“既要连通，又要省钱”这类优化目标时，最小生成树往往是最快出结果的模型。
4.3 调度与依赖：拓扑排序的实际用场
前面提过课程排课用拓扑排序，其实它还能用于编译器的编译顺序、包管理器的依赖安装、任务调度里的执行顺序判断。拓扑排序的能力在于：只要系统里的依赖关系是有向无环的，就能给出一个可执行的顺序；如果排不出来，说明存在循环依赖。
在检测循环依赖这件事上，拓扑排序非常高效。我记得有个项目，几百个微服务之间存在配置依赖，上线前需要校验一遍有没有循环。把服务列表和依赖关系构建成一个有向图后，跑一次 Kahn 算法，只要输出顶点数少于总服务数，立刻就能定位到剩下的那部分服务构成了环。后来我们把它做成了一个上线前的流水线检查项，效果比人工审查可靠得多。
还有一种变形叫“字典序最小的拓扑排序”，思路是把 Kahn 里的普通队列换成优先队列，按编号优先输出。某些竞赛题会考察这个变体，工程里例如需要按依赖顺序输出对用户最友好的安装列表时，也很实用。
5. 学习图论的路线与资料，以及我踩过的坑
5.1 先确定你的目标：是考试、算法竞赛，还是应用建模
学习图论最容易犯的错误是目标模糊，既想应付考试，又想打竞赛，还想解决工程问题，结果哪一头都学不深。我建议先明确主路线。
如果目标是考试和期末复习，重点是定义、定理和基本算法。不仅要会写代码，还要会证明，比如握手引理、欧拉回路条件、最短路径算法的正确性分析。这个阶段，把教材例题和课后题吃透就够了。热搜里常见的《图论及其应用》等教材，后面设了很多思考题，值得一道一道做。网上很多人找课后题答案，我可以理解，但我的建议是：先自己推一遍，实在卡住了再看答案，否则考试分数不会陪你说谎。
如果目标是算法竞赛，重点完全不同。你要非常熟练地掌握 BFS、DFS、Dijkstra、拓扑排序、并查集、最小生成树，再加上二分图匹配、强连通分量、网络流这些进阶内容。这个目标要靠大量刷题，而不是看教材。
如果目标是工程应用，重心又变了。你需要的是建模能力：把业务问题翻译成图语言，清楚知道什么规模该用什么算法，以及如何设计数据存储和预处理来支撑图的查询。数学定理反而可以暂时放一放，用到再补。
5.2 参考资料怎么用：从“图论及其应用”到“图论与网络最优化算法”
市面上图论教材很多，风格差别也很大。《图论及其应用》这类教材，逻辑严密、定义清晰，适合从头到尾系统地读，尤其是定理的推导过程，读一遍能建立非常扎实的理论底子。但它的缺点也很明显：代码偏少，应用场景停留在纸面，看完容易觉得“道理我都懂，代码写不出”。
《图论与网络最优化算法》则是偏运筹和工程的书，会讲最大流、最小费用最大流、匹配问题这些优化算法，而且很多算法配有数值算例。这类书适合已经有一定图论基础、想去解决实际优化问题的人。我的个人经验是：第一遍学图论，先读前一种教材的前几章；等需要解决现实工程问题，再翻开后一种教材去查对应算法，像查手册一样用。
千万不要一上来就囤一堆 PDF，然后全部吃灰。我做笔记的习惯是：每学一个算法，在笔记本上写三行——算法解决什么问题、核心步骤是什么、复杂度是什么。考试前只看这三行，就能快速回忆起来。
5.3 刷题与实践建议
如果目标是掌握到“能上手”的程度，光看书不写题绝对不行。我当初刷图论的顺序是这样的，你可以参考：
第一梯队：图的基本遍历。做连通分量计数、无向图里的环检测、有向图里的路径查找。这个阶段主要练 BFS 和 DFS 的代码熟练度，确保邻接表写得不卡壳。
第二梯队：最短路径。从无权图的 BFS 最短路开始，再到 Dijkstra，再到 Floyd。每个算法都要找到一个经典题练一遍。练习时顺手把“直径”“离心率”一起算了，这块练熟对考试很管用。
第三梯队：拓扑排序、并查集、最小生成树。这三个是高频考点也是实用工具。拓扑排序配合入度数组，并查集配合路径压缩，最小生成树用 Kruskal，大概一周就能熟练。
第四梯队：进阶内容，二分图匹配、强连通分量 Tarjan、网络流最大流。这些可以按需要选学。竞赛选手建议全学，工程方向的同学遇到匹配问题再学也不迟。
实际项目里如果一时找不到练手场景，可以把 GitHub 上开源的依赖分析工具、知识图谱构建工具拿来看一看，它们内部大量使用了图算法。自己照着实现一个小版本，比做一百道虚拟题目感受更深。
5.4 常见误区清单
最后分享几个我在教学和项目里反复遇到的坑。第一个是存储选型不当：小图用矩阵没毛病，大图强行用矩阵，算法没跑就先被空间复杂度卡死。第二个是把有向图当成无向图处理，或者反过来，最经典的翻车案例是做题时给无向图的边只加了一次，导致后面所有结果全错。第三个是初始化距离数组时忘了加大数，导致松弛时用了错误的上界，比赛中这个错误特别常见。第四个是不考虑图的连通性，题目没说图连通，你默认它连通，跑完才发现有些顶点压根没访问到。
还有一条我非常想强调：不要只背代码模板，要背背后的“为什么”。比如 Dijkstra 为什么不能处理负权边？因为它的贪心策略建立在“当前距离最小的点不可能再被更小的路径更新”这个前提上，一旦有负权边，这个前提就被打破了。你理解了这一点，面试时被问到变体题目，就不会手足无措。
图论的学习曲线确实有点陡，但只要抓住“建模 + 选存储 + 选算法”这条主线，把一个一个具体的小应用跑通，它就能从课本里走下来，变成你手里真正顺手的工具。我自己的体会是，图论最迷人的地方不是它有多抽象，而是它总能在你最意想不到的业务场景里，给你一个精确的、可计算的角度，去审视那些复杂的连接和依赖。上面这套合集，是我根据课堂内容和实践反复浓缩出来的精华，希望对正在走这条路的人有一点帮助。
