图算法核心要点全解析：邻接表、最短路径与拓扑排序实战指南

翻开教材3.7这一节往往是整门数据结构课程的坎。图的相关算法不像排序、查找那样有一个明确的套路它是在一堆节点和边的关系上做文章遍历、最短路径、生成树、拓扑排序每个算法都有自己的适用前提和边界条件。我当年学到这一节的时候最大的感受是单独看每个算法都能看懂一旦做题或者拿到实际场景里就不知道该用哪个。这篇内容就是围绕图相关的核心算法展开的从存储结构到遍历再到最短路径、最小生成树、拓扑排序最后补一些实战里最容易踩的坑。适合正在啃教材的学生、准备面试的求职者以及工作中要处理依赖关系或者路径规划这类问题的工程师。这篇的价值在于把什么时候该用哪个算法这条线讲透而不是再复述一遍教科书上的证明过程。1. 建图先于算法存储结构选错后面全白做图算法里的大多数代码本质上都是在遍历邻居这件事上做文章。所以图的存储方式决定了遍历邻居的开销也就直接决定了整个算法能不能跑起来。最常见的两种存储结构是邻接矩阵和邻接表我对这个选择的体会是很多代码写起来不对或者复杂度莫名变高问题都出在这个最容易被忽略的第一步。1.1 邻接矩阵简单直观但别乱用邻接矩阵就是一个二维数组matrix[i][j] 表示从节点 i 到节点 j 是否有边或者边的权重是多少。在没有边的位置填 0 或者一个很大的数 INF。它的优点是写起来极其简单判断任意两个节点是否相连时间复杂度是 O(1)这是它最大的卖点。但它的缺点是空间固定是 V 的平方这里的 V 是节点数。如果图有 10000 个节点直接就是 1 亿个格子每个格子如果是 4 字节的 int那就是 400 MB 内存起步。这在工程上是不可接受的。所以邻接矩阵只适合节点数非常少比如几百个以内、且图本身比较稠密的场景。所谓稠密就是边的数量接近 V 的平方级别。如果是一张稀疏图用邻接矩阵就是在用空间换一个根本用不上的快速判断两点相连的能力。我在处理实际数据时几乎没有用过邻接矩阵因为现实里的图比如社交网络的关系图、路网、任务依赖图基本都是稀疏的。每个节点平均连接几个到几十个其他节点跟总节点数比起来边数少得可怜。这种时候邻接矩阵就是纯粹的浪费。1.2 邻接表工程里的默认选择邻接表的思路是每个节点维护一个列表列表里存的是它能到达的邻居。比如节点 0 连到 1、2、3那就有一个数组或者链表存着 1、2、3。如果需要带权重就把邻居节点和权重一起存进去。这么做的好处非常直接遍历一个节点的所有邻居时只需要遍历它的列表总时间复杂度是所有节点的出度之和也就是 O(E)E 是边数。内存占用同样只有 O(V E)对稀疏图极其友好。看一个最简单的 Python 建图示例用列表存邻接表# 假设 n 个节点edges 里是 [u, v] 表示 u 到 v 有一条边 n 5 graph [[] for _ in range(n)] for u, v in edges: graph[u].append(v) # 如果是有向图上面这一行就够了 # 如果是无向图还需要加一行graph[v].append(u)带权重的话就把节点和权重的元组存进去# [u, v, w] 表示 u 到 v 有一条权重为 w 的边 for u, v, w in edges: graph[u].append((v, w))这是我的默认写法。在 C 里就是vectorvectorint或者vectorint g[N]思路完全一样。只要没有特殊说明需要频繁判断任意两点是否相连我都会选邻接表。大部分算法题和工程项目里邻接表的性能都远好于邻接矩阵。1.3 什么时候需要特殊存储除了这两种常规方式还有几个不常见但值得知道的变体。一种是边集数组就是把所有边直接放在一个数组或者列表里每条边是一个三元组 (u, v, w)。这种存储方式不关心节点之间的邻接关系只关心有哪些边所以在 Kruskal 最小生成树算法里会用得比较多因为它要对边排序。另一种是链式前向星这是竞赛圈常用的写法。它本质上是用数组模拟链表把邻接表实现得更紧凑遍历速度更快。但对大多数场景来说用向量或二维列表就够了没必要牺牲可读性去追求这一点性能。还有一个很容易被忽略的点如果节点的编号不是从 0 开始的连续整数或者节点本身是字符串那通常需要先做一次离散化把节点映射成 0 到 V-1 的整数。很多人在做题时直接拿字符串当索引结果代码写得非常别扭。我一般会用一个哈希表比如 Python 里的字典先把所有节点名映射成整数再开始建图。这个小步骤能省掉后面大量的麻烦。2. 遍历不只是走一遍DFS与BFS的真正分歧点图的遍历是几乎所有图算法的基础。DFS深度优先搜索和 BFS广度优先搜索看起来只是在走法上不同一个往深了走一个往浅了扩散但它们在实际应用里的定位差异非常大。我刚开始学的时候以为它们只是顺序不同后来才发现选哪个遍历方式直接决定了你能不能高效解决某类问题。2.1 用递归还是显式栈DFS的实现细节DFS 的思路是从一个节点出发沿着一条路径走到尽头再回头走另一条路径。实现上可以用递归函数自己调用自己def dfs(u, visited, graph): visited[u] True # 处理当前节点 for v in graph[u]: if not visited[v]: dfs(v, visited, graph)递归版本写起来最直观但它有一个隐患当图的节点数非常大比如 10 万甚至 100 万的时候递归深度可能超过语言或运行环境的默认限制导致栈溢出。Python 的默认递归深度大约是 1000 层真遇到深链的图轻轻松松就爆了。这种情况下要么手动调大递归限制要么改用显式栈模拟def dfs_iterative(start, graph): visited set() stack [start] while stack: u stack.pop() if u in visited: continue visited.add(u) # 处理当前节点 for v in graph[u]: if v not in visited: stack.append(v)这个版本的顺序会和递归版本略有差异因为栈是后进先出的但遍历到的节点集合是一样的。工程上如果需要用 DFS我一般优先考虑显式栈省得递归深了出问题。2.2 BFS与最短跳数的天然联系BFS 用队列实现一层一层往外扩散。它的一个极其重要的性质是在无权图或者说所有边的权重相同中BFS 第一次到达某个节点时走的路径一定是最短的这里的最短指的是经过的边数最少或者跳数最少。这个性质在很多场景里可以直接拿来用。比如社交网络里计算两个人之间隔着几层关系再比如迷宫里找从起点到终点的最少步数。只要图是等权的直接用 BFS 就能拿到最短跳数根本不需要上 Dijkstra 这种更复杂的算法。Dijkstra 本质上就是有权版本的 BFS先把这条线理解清楚了后面学 Dijkstra 会顺很多。BFS 的模板代码很固定from collections import deque def bfs(start, graph): visited [False] * len(graph) dist [-1] * len(graph) q deque([start]) visited[start] True dist[start] 0 while q: u q.popleft() for v in graph[u]: if not visited[v]: visited[v] True dist[v] dist[u] 1 q.append(v) return dist这里的 dist 数组记录每个节点的最短跳数。BFS 第一次碰到节点 v 时dist[v] 就是最终答案不需要后续再更新。2.3 遍历顺序干扰下的visited标记坑有一个问题我栽过好几次什么时候标记 visited 才合适大多数人会在节点入队或入栈时才标记但更稳妥的是在把邻居加入队列时顺便标记否则在有些图结构里同一个节点可能被多次放进队列导致重复处理虽然最后结果可能没错但效率会差很多甚至在某些统计问题里会算出重复的答案。还有一个常见误区是DFS 里递归函数的开头已经标记了 visited但相邻节点在循环里又忘了判断结果出现循环依赖栈溢出或者死循环。每次写遍历我都习惯先想清楚三件事visited 在哪一步标记、邻居在哪一步判断、有没有可能重复访问。想明白了这三个问题遍历代码一般不会出大错。3. 最短路径三件套Dijkstra、Bellman-Ford、Floyd的取舍最短路径问题是图算法里最出圈的一个因为它的应用太常见了地图导航找最快路线、网络路由选择延迟最低的路径、物流系统规划运输成本最低的线路。但最短路径并不是一个算法通吃单源和多源、有没有负权边、图稠密还是稀疏这些条件决定了你该从哪个算法下手。3.1 Dijkstra贪心在有向非负权图上的胜利Dijkstra 解决的是从一个起点到其他所有节点的最短路径前提是所有边的权重不能为负数。它为什么不能处理负权因为它的核心策略是贪心每次从还没确定最短路的节点里取出当前距离最小的节点认定它的最短路已经确定了然后拿它去更新邻居。这个策略在非负权图下是安全的因为任何绕路去更新该节点的路径都不可能比当前距离更小。但一旦出现负权边就可能出现一条先走远路、再被负权边拉回来的路径距离反而更小。此时贪心直接失效。我当年在做题时被一道带负权边的题坑过用了 Dijkstra结果几乎每条答案都差那么一点点怎么都想不通后来才发现是算法选错了。算法实现上朴素版 Dijkstra 每次要找最小距离节点复杂度是 O(V²)。但在稀疏图里用优先队列优化一下效率会好很多。配合堆的版本核心代码如下import heapq def dijkstra(start, graph, n): INF 10**18 dist [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注意两件事优先队列里存的是 (距离, 节点)因为 Python 的堆默认按元组第一个元素排序第二件事是if d dist[u]: continue这行的作用。因为一个节点的 dist 可能在入堆之后又被更短的路径更新堆里会残留一些过期的旧距离记录弹出时发现它不是当前最小值直接丢弃。没有这行会多处理很多无效节点但结果依然是对的只是慢。3.2 Bellman-Ford为负权边而生Bellman-Ford 解决同样的问题但它允许图中存在负权边。它的思路简单粗暴对所有边进行松弛操作所谓松弛就是看能不能通过当前节点让邻居的距离更小。重复做 V-1 轮每一轮都尝试用所有边更新距离。在一个没有负环的图里最短路径的边数最多是 V-1 条所以 V-1 轮松弛之后所有节点的最短距离就稳定了。代码上非常简洁用上一步提到的边集数组最方便def bellman_ford(n, edges, start): INF 10**18 dist [INF] * n dist[start] 0 for _ in range(n - 1): for u, v, w in edges: if dist[u] ! INF and dist[u] w dist[v]: dist[v] dist[u] w # 再试一轮如果还有更新说明存在负环 for u, v, w in edges: if dist[u] ! INF and dist[u] w dist[v]: return None # 存在负环 return dist很多同学不理解为什么是 V-1 轮。打个比方最短路的形成就像信息传播每一轮松弛只保证信息在路径上最多往后传一条边。一条路径最多经过 V 个节点也就是最多 V-1 条边所以传 V-1 轮所有最短路里的边都能被覆盖到。如果第 V 轮还能继续更新说明存在一个永远能让距离变小的环也就是负环这时候最短路就没有意义了。Bellman-Ford 的缺点是慢复杂度 O(V·E)。在图上很容易超时。它最大的价值其实不是算最短路而是判断有没有负环以及作为一个理论上的兜底方案。3.3 Floyd多源最短路径的暴力美学如果要求所有节点对之间的最短路径Floyd 是最好写的算法没有之一。三层循环中间节点 k、起点 i、终点 j不断更新 dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])。核心就这一句话。def floyd(n, 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]dist 初始就是邻接矩阵有边的地方存权重无边的地方存 INF自己到自己存 0。Floyd 能处理负权边只要没有负环就行。它的复杂度是 O(V³)所以只适合节点数在几百量级的场景再多就会跑不动。三个算法怎么选我的经验是场景推荐算法原因单源、非负权、稀疏图Dijkstra 优先队列快O(E·logV)单源、可能有负权边Bellman-Ford能处理负权边还能检测负环多源、节点数小Floyd代码简单逻辑直白全部算出单源、非负权、稠密图朴素 DijkstraO(V²)稠密图下比堆优化更好写效果也更好最后一行的判断挺反直觉的很多人觉得堆优化肯定更快。但稠密图里边数接近 V²堆优化的 O(E·logV) 反而会比 O(V²) 更大。所以算法选型真的要看数据范围不能无脑堆优化。4. 造路的学问Prim与Kruskal如何安全圈地最小生成树解决的问题是在一个带权无向连通图里选出一组边把所有节点连起来同时让边的总权重最小。这个问题的应用场景非常接地气铺设电缆连接所有村庄、建设通信基站之间的光缆网络、规划供水管道的最小总长度。它的本质是用最小的成本把孤岛连成整体我管这叫安全圈地。最小生成树有两个经典算法Kruskal克鲁斯卡尔和 Prim普里姆。它们思路差异很大但殊途同归。4.1 Kruskal排序加并查集思路直白Kruskal 的思路可以概括为把所有边按权重从小到大排序然后一条边一条边地看如果这条边连接的两个节点目前还不属于同一个连通块就把它选进生成树。为什么这样选出来的结果一定是最小生成树这个结论背后是切割定理在任意一个时刻把节点分成两块跨过这两块之间的最短那条边一定属于某棵最小生成树。Kruskal 每次选的都是当前连接不同连通块的最短边正好符合切割定理的条件。实现上最重要的一点是要能快速判断两个节点是否在同一个连通块这就要用到并查集。代码结构大概是# 并查集部分 parent list(range(n)) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x def union(a, b): ra, rb find(a), find(b) if ra ! rb: parent[ra] rb return True return False # 主流程 edges.sort(keylambda e: e[2]) mst_weight 0 for u, v, w in edges: if union(u, v): mst_weight w如果最后选出来的边数少于 V-1说明图不连通也就不存在覆盖所有节点的生成树。Kruskal 的时间主要花在排序上复杂度是 O(E·logE)。它适合边比较稀疏的图因为排序成本相对可控。4.2 Prim从单个点长出一棵树Prim 的思路不一样从一个节点出发维护一个已经在树里的集合然后每次找一条连接树内和树外节点的最短边把对面的节点加进树里。重复 V-1 次所有节点就都进树了。它和 Dijkstra 看起来特别像区别在于更新的依据不同。Dijkstra 更新的是到起点的距离Prim 更新的是到当前树集合的最短距离。朴素版 Prim 的实现def prim(n, graph): INF 10**18 dist [INF] * n # 每个节点到已选集合的最短距离 visited [False] * n dist[0] 0 mst_weight 0 for _ in range(n): u -1 for i in range(n): if not visited[i] and (u -1 or dist[i] dist[u]): u i if u -1: return None # 图不连通 visited[u] True mst_weight dist[u] for v, w in graph[u]: if not visited[v] and w dist[v]: dist[v] w return mst_weight朴素版复杂度是 O(V²)和邻接矩阵配合起来在稠密图上效果很好。如果想用堆优化可以像 Dijkstra 那样加优先队列复杂度到 O(E·logV)适合稀疏图。4.3 两种算法在实际工程里的选择依据很多教材都会说 Kruskal 适合稀疏图、Prim 适合稠密图这句话在理论上是对的但工程上还有别的考虑维度。Kruskal 的优点是算法思路完全不用管图长什么样只要拿到所有边的列表就能算而且并查集极好写。它不依赖图的遍历能力所以很多时候实现成本低。Prim 则必须建立在从某个节点开始扩散的模型上需要能快速找到一个节点它的所有邻居。如果图的存储是邻接表Prim 天然就好用。我自己的习惯是能做边的排序就直接用 Kruskal简单不容易错。只有当图特别稠密、边数接近完全图的时候我才考虑用朴素 Prim 来绕开排序的开销。另外还有一个冷门但实用的技巧如果题目要求输出最小生成树由哪些边构成Kruskal 天然就输出边列表往往更方便。5. 拓扑排序不止于排序从依赖图到任务调度拓扑排序是图算法里应用最工程化的一个。它的场景很明确你有一堆任务任务之间有先后依赖关系比如先完成 A 才能开始 B要求找出一个合法的执行顺序。把这种依赖关系建模成有向图每个节点是一个任务每一条边 A - B 表示 A 必须在 B 之前完成。如果整个图能够排出一种顺序让所有边都从前面的节点指向后面的节点这种顺序就是拓扑序。5.1 一个有向无环图才能排出的顺序拓扑排序的难点在于并不是所有有向图都有拓扑序。如果图里存在环比如 A - B、B - C、C - A那这三个任务互相依赖永远找不到合法的先后顺序。所以拓扑排序只能作用在有向无环图DAG上。Kahn 算法是最常用的实现方式思路很好理解一个节点能被执行前提是它的所有前驱节点都已经执行过了。换句话说如果一个节点的入度为 0它就没有任何前置依赖可以直接排进顺序。执行完之后它指向的那些邻居的入度都要减一减到 0 的邻居就变成了新的可执行节点。from collections import deque def topo_sort(n, graph): indeg [0] * n for u in range(n): for v in graph[u]: indeg[v] 1 q deque([i for i in range(n) if indeg[i] 0]) result [] while q: u q.popleft() result.append(u) for v in graph[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) if len(result) ! n: return None # 有环无法拓扑排序 return result我特别喜欢 Kahn 算法的一点是它用队列模拟了一个就绪队列的概念这和操作系统的进程调度、构建系统里的任务调度几乎一一对应。理解了一个就等于理解了另一个。5.2 环检测拓扑排序的真正价值拓扑排序在很多场景里的最大价值不是排出一个合法顺序而是判断能不能排出来。如果图里有环说明任务之间存在循环依赖整个调度根本无法成立。回到 Kahn 算法的最后一步如果排出来的节点数少于总节点数那就说明有节点永远进不了队列因为它始终有入度无法清零也就是存在环。这一步判断非常便宜却特别有用。我记得有一次需要处理一批模块的编译顺序模块之间有一堆互相引用的关系。我一开始直接按名字排序结果编译时报了一堆循环依赖的错误。后来改成先建依赖图跑一遍拓扑排序很清楚地定位到是哪个模块互相引用了才彻底解决问题。工程上依赖不能成环是一个硬约束拓扑排序就是检测这个约束的利器。5.3 常见场景编译顺序、任务编排拓扑排序的应用远不止课程作业。构建工具里源文件之间的 include 依赖决定了编译顺序本质是拓扑排序。包管理器里库之间的依赖关系要先解析才能确定安装顺序这也是拓扑排序。数据流水线里一个计算任务依赖另一个计算任务的输出调度系统也要先做拓扑排序。这类题的一个变形是如果存在多个合法拓扑序要求输出字典序最小的那个。做法也很简单把 Kahn 算法里的普通队列换成优先队列每次优先取编号最小的入度为 0 的节点。我之前在处理任务编排时用过这个变形为的是让输出顺序更稳定、更符合直觉。这个小技巧值得记下来。6. 刷了那么多图最后还是栽在这些细节上图算法的大框架学完之后真正决定代码能不能一次性写对、能不能在时限内跑完的往往是一些小细节。我把自己反复踩过的坑集中整理了一下这些细节看似不起眼但每一条都让我浪费过不少时间。6.1 用0还是用INF初始化dist数组最最容易踩的坑就是距离数组的初始值。如果图里边的权重可能很大比如 10 的 9 次方而你把 INF 设成 10 的 6 次方那在松弛比较dist[u] w dist[v]时u 的可达距离加上 1 亿可能会直接超过 int 的范围产生溢出或者让本应更新的路径被错误跳过。所以我现在的习惯是INF 至少设成题目给的最大可能距离乘个 2 到 3 倍用 Python 就直接用10**18用 C 就用LLONG_MAX / 4。用一个足够大的数比每次猜够不够大要稳得多。另一个细节是无向图的矩阵初始化时对角线要设为 0没有边的位置设为 INF。如果对角线不设 0Floyd 跑出来的结果会莫名其妙多出一些自环路径的干扰。6.2 稀疏图和稠密图的最短路实现选择我在前面提过 Dijkstra 的堆优化和朴素版选择问题这个坑在工程里会放大得特别明显。有一回我处理一个节点极少但边几乎写满的稠密图用了堆优化的 Dijkstra结果发现优先队列里的节点被反复更新堆里的元素数量膨胀得比预想大很多虽然最后还是跑完但效率明显不如朴素版 O(V²) 扫一遍。反过来说在 E 接近 V 的稀疏图里堆优化基本是碾压级别的快。所以选算法之前请务必先看清楚边的数量级。如果题目没有明确说明 E 的范围我建议先看节点的数据范围做一个预估V² 和 E·logV 哪个算起来更小就选哪个。6.3 真题拆解一个地铁换乘问题接下来用一个综合例子把这些算法串起来。假设给你一张地铁线路图站台是节点站与站之间是边边权是两站之间的通行时间现在要算从起点站到终点站最短要花多久。这个题看起来直接套 Dijkstra 就行但地铁场景有一个特殊约束换乘是有额外时间的。从一个公司的线路换到另一个公司的线路中间要步行、等车这部分时间不能简单算成一条边。怎么建模一个常见的做法是把每个站拆成多个状态节点比如在这个站属于线路 A和在这个站属于线路 B是两个不同的节点。站内换乘就变成从线路 A 的节点到线路 B 的节点的一条边权重是换乘时间。这样建出来的图还是普通的带权图照样能用 Dijkstra 求解。这个例子想说明的是很多实际问题难点不在于算法本身而在于怎么把场景抽象成图。抽象对了最后跑的算法往往就是最基础的那几个。我整理这些细节的时候反复强调先建图再选算法原因也在这里。至少在我接触过的项目里图的算法并不复杂复杂的是识别出这是个图论问题并把规则翻译成边权。把那一步做对了剩下的就是按部就班地写模板代码。