★ FEATURED ARTICLE 图论这门东西我最早接触是在做路径规划的时候。当时手头有个需求要在几十个节点之间找一条代价最小的走法我第一反应是写个递归去穷举结果节点数刚过二十程序就跑了一整夜还没出结果。后来一位做算法的朋友看了我的代码只说了一句“你这是在用蛮力解一个图论问题。”那是我第一次意识到图论不是课本上那些画着圆圈和连线的插图而是一套能直接把“关系”变成“计算”的语言。这篇内容我想把图论里那些最基础但最容易被人含糊带过的概念用从业者的视角重新捋一遍——它们分别解决什么问题、在代码里长什么样、新手最容易在哪几个地方栽跟头。不管你是刚翻开离散数学教材的学生还是写业务代码时突然要处理依赖关系、社交网络、任务调度的开发者这些概念都是绕不开的地基。1. 图论到底在建模什么从“关系”到“点与线”很多人学图论的第一道坎不是算法而是没搞明白图到底在描述现实世界里的什么东西。教材上定义“图由顶点和边组成”这句话没错但它太抽象了抽象到你看完还是不知道什么时候该用它。1.1 图是一种把“关系”抽象成结构的工具我习惯这样理解图是用来描述“一堆对象以及对象之间联系”的数学结构。这里的“对象”就是顶点“联系”就是边。关键在于图刻意忽略了对象的其他所有属性只保留“谁和谁有关系”这一层信息。这种“只留关系、丢掉细节”的抽象恰恰是图论强大的地方。举个我实际遇到过的场景。某次要做一套课程先修关系的校验系统课程有几十门每门课可能有若干门前置课。如果用表格存你得反复查“这门课的前置课的前置课是什么”写起来又臭又长。但把它画成图每门课是一个顶点一条“A 是 B 的前置课”就是一条从 A 指向 B 的有向边整个先修体系立刻变成一张有向图判断“是否存在循环依赖”就等价于判断“图里有没有环”。问题从“查表”变成了“图上的结构判断”这就是建模的价值。所以判断一个现实问题该不该用图来建模我的经验标准很简单当问题的核心是“实体之间的连接关系”而不是实体本身的数值属性时就该考虑图。社交网络是人和人的关注关系交通网络是地点和地点的通行关系任务调度是任务和任务的先后依赖关系这些全都是“关系”主导的问题。1.2 顶点和边图的两个基本原子顶点vertex也叫节点 node代表被研究的对象边edge代表对象之间的联系。这两个词看起来简单但真正写代码时第一个要做的决策就是顶点用什么表示边用什么表示。顶点的表示相对直接通常用一个唯一标识符比如整数编号、字符串 ID。边则复杂一些因为它天然带有“方向”和“权重”两个可选属性这两个属性决定了你该用哪种图模型。边的属性含义典型场景无向、无权只表示“有联系”朋友关系、无向道路有向、无权表示“单向联系”关注关系、先修依赖无向、有权联系带代价双向等价双向道路里程有向、有权单向联系带代价单行道、带权依赖我见过不少新手一上来就用“带权有向图”去套所有问题觉得功能最全最保险。这其实是个坑多余的属性会让算法和调试都变复杂。如果业务里朋友关系就是对称的老老实实用无向图别为了“以后可能用得上”硬加方向否则后面判断连通性时你还得自己保证对称性不被破坏纯属给自己找麻烦。1.3 为什么“只保留关系”反而更强这里我想多说一句容易被忽略的认知。初学者常觉得图论“信息量太少”因为顶点和边丢掉了对象的很多属性。但恰恰是这种“少”让图论能跨领域通用。同一套最短路算法既能算地图导航也能算网络路由还能算任务调度的最小代价路径因为它们抽象出来的结构完全一样。提示建模时先问自己“我要研究的对象是什么、它们之间什么算‘有联系’”把这两个问题答清楚顶点和边自然就定下来了。不要一上来就纠结用哪种图先把关系理清楚。2. 有向与无向、加权与无权选错图类型会带来什么后果图类型的四个组合我在上一节列了表但光知道分类没用真正的问题是选错了会怎样。这一节我用两个真实踩过的坑来说明选错图类型不是“多此一举”而是会直接导致结果错误或者代码难维护。2.1 无向图当成有向图连通性判断会漏早些年我做一个“群组内好友推荐”的功能好友关系本质是无向的——A 是 B 的好友B 必然是 A 的好友。但我当时图省事底层统一用了有向图结构存储插入关系时只插了 A 到 B 这一条边忘了插反向边。结果做连通分量统计时程序认为 B 和 A 不在同一个连通块里推荐结果错得离谱。这个坑的根因在于无向图的一条边在有向图里必须用两条方向相反的边来模拟。如果你用有向结构存无向关系就必须在插入、删除时严格保证两条边同步任何一处漏掉都会破坏“对称性”这个隐含契约。我的建议是如果关系天然对称直接用无向图的数据结构让结构本身帮你保证对称而不是靠人肉维护。2.2 无权图硬套权重算法选型会被带偏另一个坑来自权重。有次做任务依赖的最短完成时间估算任务之间的依赖本身没有“代价”但我为了“通用”给每条边都塞了个默认权重 1。表面看没问题可后来要算“关键路径”时我发现自己在用一个带权最短路算法去解一个本该用拓扑排序加动态规划的问题绕了一大圈还因为默认权重掩盖了真实的依赖层级关系结果对不上。教训是权重不是“有总比没有好”的东西它代表一种额外的语义。当业务里根本没有“代价”这个概念时强行加权重会让算法选择偏离问题本质。无权图有它自己的、更简洁的算法比如 BFS 求无权最短路这些算法在无权场景下比带权算法更快也更不容易出错。2.3 一张对照表帮你快速定类型我把常见的判断逻辑整理成下面这张表实际建模时对着走一遍基本不会选错判断问题是否关系是否对称无向有向关系是否带代价/距离/权重加权无权是否需要区分“从谁到谁”有向无向举个综合例子城市之间的高速公路如果都是双向通行且关心里程那就是无向加权图如果存在单行道就得升级成有向加权图如果只关心“能不能到达”而不关心距离那加权属性可以砍掉退化成无权图算法能简化不少。注意图类型不是越复杂越好。每多一个属性方向、权重你的数据结构、算法实现、测试用例都要跟着变复杂。能用简单模型解决的问题绝不要上复杂模型。3. 度、路径、连通性三个最容易被“想当然”的概念这三个概念几乎每本教材都会讲但恰恰因为它们“看起来太简单”很多人在实际用的时候会想当然结果在边界情况上翻车。我挑三个最典型的误区来讲。3.1 度有向图里必须区分入度和出度无向图里一个顶点的度就是和它相连的边数很直观。但到了有向图度必须拆成入度指向该顶点的边数和出度从该顶点出发的边数。这个区分不是学术洁癖而是有实际后果的。我做过一个依赖解析器需要找出“没有任何前置依赖、可以立即执行”的任务。正确的判断是入度为 0因为入度代表“有多少东西指向我”也就是“我依赖了多少东西”。当时有个同事写成了“度为 0”在有向图里这个说法本身就不严谨他实际算的是入度加出度结果把一些“虽然没人依赖它、但它自己依赖别人”的任务也误判成了可立即执行导致执行顺序错乱。所以记住这个对应关系入度 依赖我/指向我的数量出度 我依赖/我指向的数量。拓扑排序里反复用到的“入度为 0 的顶点入队”靠的就是这个语义。3.2 路径与简单路径环的存在会改变一切路径是一串首尾相连的边。这里有个关键区分简单路径要求路径中不重复经过任何顶点。为什么这个区分重要因为一旦图里存在环路径就可以无限绕圈很多算法比如最短路如果不限制“简单”理论上根本没有终止条件。我在写一个流程校验工具时就吃过亏。需求是判断“从起点能否走到终点”我随手写了个 DFS没做访问标记结果图里有个环程序在环里死循环栈直接爆掉。修复方式很简单DFS 时维护一个已访问集合遇到访问过的顶点就跳过。这个“已访问集合”本质上就是在保证我们走的是简单路径。3.3 连通性无向叫连通有向叫强连通连通性是最容易混淆的地方因为无向图和有向图的定义完全不同。无向图任意两个顶点之间都存在路径就叫连通图否则分成若干个连通分量。有向图任意两个顶点 u、v 之间既存在 u 到 v 的路径又存在 v 到 u 的路径才叫强连通对应的有强连通分量。差别在哪有向图里“u 能到 v”不代表“v 能到 u”。我见过有人把无向图的连通分量算法直接搬到有向图上算出来的“分量”其实是“从某点出发能到达的所有点”这跟强连通分量完全是两码事。判断有向图的强连通标准做法是 Tarjan 或 Kosaraju 算法它们专门处理“双向可达”这个更强的条件。概念适用图类型核心要求连通 / 连通分量无向图任意两点间存在路径强连通 / 强连通分量有向图任意两点间双向可达弱连通有向图忽略方向后连通提示拿到一个有向图要分析连通性时先明确你要的是“单向可达”还是“双向可达”。这两个答案经常不一样用错算法结果会差很远。4. 图的存储邻接矩阵和邻接表不是随便挑一个概念理清之后落到代码上第一个绕不开的决策就是存储结构。邻接矩阵和邻接表是最常见的两种网上教程往往只说“稠密图用矩阵、稀疏图用表”但实际选型时还有几个更细的考量我结合自己的使用经验展开讲。4.1 邻接矩阵查询快但空间是硬伤邻接矩阵用一个 V×V 的二维数组表示matrix[i][j]存 i 到 j 是否有边或边的权重。它的优点是判断两点之间是否有边是 O(1)实现也极其简单一个二维数组搞定。但它的空间复杂度是 O(V²)这个代价在顶点数大时会非常致命。我做过一个顶点数上万的稀疏图项目一开始图省事用了邻接矩阵结果光存储就占了上百 MB而且绝大部分格子是空的因为边很少。后来换成邻接表内存直接降了两个数量级。所以邻接矩阵的适用场景很明确顶点数不大通常几百以内且边比较稠密。比如一些小规模的完全图、状态转移图用矩阵反而清晰高效。4.2 邻接表稀疏图的默认选择邻接表给每个顶点维护一个列表存它所有邻居。空间复杂度是 O(VE)在稀疏图E 远小于 V²下优势巨大。绝大多数实际业务里的图都是稀疏的——社交网络里一个人平均好友数远小于总人数路网里一个路口连接的道路也就几条。邻接表的代价是查询“i 和 j 是否有边”需要遍历 i 的邻居列表最坏 O(度)。如果你的算法频繁做这种点对点查询邻接表会慢。但对于遍历类算法BFS、DFS、最短路邻接表反而是最自然的因为算法本来就是“从一个点出发看它的所有邻居”。下面是我常用的邻接表 Python 实现骨架用字典套列表兼顾灵活和直观# 邻接表graph[u] 存 u 的所有邻居可带权重 graph {} def add_edge(u, v, weightNone): graph.setdefault(u, []) graph.setdefault(v, []) if weight is None: graph[u].append(v) else: graph[u].append((v, weight)) # 示例构建一个带权有向图 add_edge(A, B, 3) add_edge(A, C, 1) add_edge(B, C, 2)4.3 选型决策先看规模再看操作我把选型逻辑总结成三步先估顶点数 V 和边数 E。如果 V 在几百以内且 E 接近 V²矩阵可以接受否则优先考虑邻接表。再看核心操作。如果算法大量做“两点间是否有边”的查询矩阵更合适如果主要是遍历邻居邻接表更合适。最后看实现成本。小规模、一次性脚本矩阵的简单性可能比性能更重要长期维护的库邻接表的空间优势更值得。维度邻接矩阵邻接表空间O(V²)O(VE)查边O(1)O(度)遍历邻居O(V)O(度)适合稠密、小规模稀疏、大规模注意还有一种“边集数组”存法把所有边存成一个列表适合 Kruskal 这类按边处理的算法。存储结构要跟着算法走没有万能解。5. 从概念到代码一次完整的图构建与遍历实操概念和存储讲完我想用一个完整的小例子把前面所有东西串起来让你看到“顶点、边、有向、邻接表、BFS 遍历”是怎么在一个真实脚本里落地的。这个例子我刻意做得小但每个环节都对应前面讲过的概念。5.1 需求判断任务依赖是否存在环假设有一组任务任务之间有先后依赖我要判断这些依赖是否构成环有环意味着任务永远无法全部完成。这是一个典型的有向图判环问题用拓扑排序基于入度就能解决。5.2 构建图并计算入度from collections import deque # 任务依赖u - v 表示 u 必须在 v 之前完成 dependencies [ (A, B), (A, C), (B, D), (C, D), (D, E), ] graph {} indegree {} def add_edge(u, v): graph.setdefault(u, []) graph.setdefault(v, []) indegree.setdefault(u, 0) indegree.setdefault(v, 0) graph[u].append(v) indegree[v] 1 # v 的入度加一因为多了一个指向它的依赖 for u, v in dependencies: add_edge(u, v)这里indegree[v] 1就是前面讲的“入度 指向我的数量”的直接体现。每个任务初始入度为 0每被依赖一次就加一。5.3 拓扑排序判环def has_cycle(graph, indegree): # 入度为 0 的任务可以立即执行 queue deque([node for node in indegree if indegree[node] 0]) visited_count 0 while queue: node queue.popleft() visited_count 1 for neighbor in graph.get(node, []): indegree[neighbor] - 1 if indegree[neighbor] 0: queue.append(neighbor) # 如果处理过的任务数少于总任务数说明剩下的任务互相依赖成环 return visited_count ! len(indegree) print(has_cycle(graph, indegree)) # 输出 False无环这段代码的核心逻辑就是不断摘掉入度为 0 的顶点摘掉后把它指向的邻居入度减一减到 0 就入队。如果最后还有顶点没被摘掉说明它们卡在环里入度永远降不到 0。这个“摘叶子”的过程本质上就是在利用入度这个概念做结构分析。5.4 实测中的两个小坑第一个坑是孤立顶点。如果某个任务没有任何依赖关系它既不出现在任何边的起点也不出现在终点上面的indegree字典里根本不会有它最后统计总数时就会漏算。修复办法是初始化时把所有任务都登记进indegree哪怕它没有边。第二个坑是重复边。如果依赖列表里出现重复的(A, B)入度会被多加一次导致判断出错。实际业务里依赖关系通常要去重或者在建图时用集合去重。这两个坑都不大但如果不注意判环结果会莫名其妙地错。6. 新手最常踩的四个概念误区与纠正最后我想集中聊几个我在带人、看代码时反复见到的概念误区。它们都不是算法层面的难题而是对基础概念的理解偏差但恰恰是这些偏差让很多人在写图相关代码时反复返工。6.1 把“边数”和“度数”搞混边数 E 是图里所有边的总数度数 deg(v) 是某个顶点连的边数。这两者的关系是所有顶点的度数之和等于边数的两倍无向图因为每条边贡献两个端点度数。有向图里则是所有入度之和 所有出度之和 边数。这个恒等式在调试时特别好用如果你算出来的度数和跟边数对不上说明建图过程有 bug边插多了或插少了。6.2 以为“有路径”就等于“连通”前面强调过有向图里“u 能到 v”只是单向可达不叫连通。我见过有人用 BFS 从起点出发能访问到终点就判定“两点连通”这在无向图里没问题在有向图里就错了——连通强连通要求双向可达。判断有向图两点是否强连通得分别从 u 和 v 各做一次可达性分析两次都成功才算。6.3 忽略自环和平行边自环是顶点指向自己的边平行边是两个顶点之间有多条边。很多教材为了简化会假设“无自环、无平行边”但真实数据里这两种情况太常见了比如用户给自己点赞、两个城市之间有多条不同线路。如果你的算法没考虑它们轻则结果偏差重则死循环。我的习惯是建图时先检查有没有自环和平行边根据业务决定是过滤掉还是保留绝不默认它们不存在。6.4 用错遍历的“已访问”标记时机DFS 和 BFS 都需要标记已访问顶点防止重复。新手常犯的错是在出队/出栈时才标记而不是入队/入栈时就标记。这会导致同一个顶点被多次加入队列虽然结果可能碰巧对但效率会退化极端情况下队列会膨胀得很大。正确做法是顶点一旦被加入待处理集合立刻标记为已访问。提示这四个误区有个共同点——它们都不是“不会写算法”而是“对概念的理解差了一层”。把度、连通、自环这些基础概念抠清楚比急着背算法模板有用得多。我在实际项目里越来越体会到图论真正难的不是那些算法名字而是建模那一步的判断什么算顶点、什么算边、要不要方向、要不要权重、用哪种存储。这些判断一旦错了后面算法写得再漂亮也是白搭。上面这些概念和踩坑经验基本都是我在建模阶段反复吃亏之后才真正记住的。如果你刚开始接触建议先拿一个自己熟悉的小场景比如课程依赖、文件引用关系手动画一遍图把顶点、边、方向、入度都标出来再动手写代码会比直接抄算法模板扎实得多。
阅读完成 · 觉得有帮助？
