数据结构学到“图”这一章才算真正撞上了算法的门槛。前面数组、链表、栈、队列、树核心都是处理“一对一”或“一对多”的关系脑子里还能画出清晰的层次结构但图完全不一样它允许任意两个节点之间都有连线能描述的关系复杂到吓人——导航软件里的路网、微信里的好友关系、编译器里的依赖解析、电商系统里的商品推荐背后全是图。我啃数据结构时最费劲的也是这一章。难不是因为它公式多而是需要同时具备“抽象建模”和“动手编码”两种能力你得先看懂一张图在表达什么再用邻接矩阵或邻接表把它装进内存最后还要把BFS、DFS、Dijkstra这些经典算法跑通。这篇文章我就站在这类“踩过坑、写过代码、也用图解决过实际问题”的角度把这章里最核心的东西重新捋一遍适合正在学数据结构的同学、准备考研408的选手以及工作中需要处理图关系的数据开发。1. 图到底是什么从“多对多”说起线性表和树之所以解决不了一些问题根源在于它们表达关系时都有“限制”。数组和链表是排队从头走到尾只能按顺序二叉树里每个节点最多挂两个子节点且一般不允许成环。图是唯一一种允许任意两个节点都产生直接联系的逻辑结构。1.1 线性、树、图数据关系三个层级你可以把这三者理解为三种不同复杂度的关系模型。单链表是一条铁链从head到尾节点只能按顺序走想回头就得从头再来。二叉树是一张组织结构图总经理下面有部门经理部门经理下面有组长每个人只有一个上级路径天然是单向、无环的。图则像现实中的地铁线路图你从任何一个站出发经过不同换乘都能到另一个站线路之间互相交叉还能绕圈子。图的形式化定义是图G由顶点集V和边集E组成记作G(V, E)。V是非空有穷集合E是连接V中顶点的边的有穷集合。这里注意树其实也是图的一种特例只是限制了“连通且无环”但课程和考试里一般单独讲树图这一章主要研究更一般、更自由的场景。1.2 有向、无向与加权关系本身也有差异边是否带方向是图的一个重要分类维度。如果边没有方向A和B之间存在一条边那么从A能到B从B也能到A这叫无向图适合描述“邻居”“朋友”“网络链路”这类天然双向的关系。如果边带方向从A能走到B除非存在一条B到A的边否则回不来这叫有向图。微博关注关系是典型你关注了一个大V但大V不一定关注你这种不对称关系必须用有向图。再看权重。每条边带上数值就是带权图。权重可以表示两个节点的距离、费用、时间或流量。不带权的图叫无权图默认每条边的权重都是1。最短路径问题里权重就是决定“最优”的关键依据没有权重就只能按“跳数最少”来算。1.3 稠密与稀疏直接决定存储方案的选择这里有两个必须搞清楚的概念它们是后面选存储结构、估算法复杂度的重要依据。第一个是边的数量级。n个顶点的无向图最多有n(n-1)/2条边。什么时候算稠密、什么时候算稀疏没有绝对标准按我的经验边的数量接近n的平方量级就是稠密接近n量级就是稀疏。城市道路网属于稀疏图而一个班级里所有学生之间都存在联系的关系网就比较稠密。第二个是连通分量。无向图里如果任意两个顶点都互相可达称为连通图否则就是非连通图它的极大连通子图叫连通分量。有向图里还要区分强连通和弱连通。这些名词在考试里出现频率很高建议自己画几个例子验证一遍光背定义容易混。2. 存储结构选型邻接矩阵还是邻接表图怎么装进计算机经典方案就两个邻接矩阵和邻接表。这一节说清楚它们在内存中是什么样的、代码怎么实现、什么场景选谁。2.1 邻接矩阵O(1)查边的代价是O(n²)空间邻接矩阵用二维数组存储。a[i][j]1表示顶点i到j有边0表示没有若是带权图就用具体权值没有边则用无穷大表示。用Python实现非常直观class GraphMatrix: def __init__(self, n, directedFalse): INF float(inf) self.n n self.directed directed self.matrix [[INF] * n for _ in range(n)] for i in range(n): self.matrix[i][i] 0 def add_edge(self, u, v, weight1): self.matrix[u][v] weight if not self.directed: self.matrix[v][u] weight注意我初始化时用了INF而不是0长度判断“没有边”时不再用0而用无穷大。这样的好处是后面跑最短路径算法时直接取min就能继续写不需要额外判断。用0表示无边只适合纯连通性判断遇到带权图一定要改用无穷大。邻接矩阵最大的优势是判断两点之间是否有边只需O(1)时间代码写起来逻辑特别直。代价是空间复杂度O(n²)顶点数到一万以上就会爆内存。我平时在本地跑实验节点超过5000就基本不考虑矩阵了。2.2 邻接表空间省了查边变慢了一点邻接表是“数组链表”的组合。每个顶点对应一个链表链表里存的是与该顶点相连的邻居以及边权。稀疏图里所有链表长度之和约等于边数m空间复杂度O(nm)比矩阵省得多。Python实现用list of list就够了class GraphList: def __init__(self, n, directedFalse): self.n n self.directed directed self.adj [[] for _ in range(n)] def add_edge(self, u, v, weight1): self.adj[u].append((v, weight)) if not self.directed: self.adj[v].append((u, weight)) def neighbors(self, u): return self.adj[u]邻接表里判断u和v之间是否有边需要遍历u的邻接链表最坏O(度)。实际算法中我们经常做的是“从某个点出发看它的所有邻居”这种场景邻接表反而是最自然的形态遍历、搜索、路径算法基本都优先用邻接表。2.3 选型建议别无脑跟风看场景挑对比维度邻接矩阵邻接表空间复杂度O(n²)O(nm)判断u、v是否有边O(1)O(度)遍历u的所有邻居O(n)O(度)适合场景稠密图、频繁查边稀疏图、大规模图实现难度低中等我自己的习惯是节点数在1000以内、边比较密集时用矩阵写起来省心节点数大、边稀疏时用邻接表内存压力小。考试写算法题我推荐邻接表因为考研代码题给的输入规模一般都不大邻接表又通用不会因为题目没说明图的密度而翻车。3. 遍历是通往一切图算法的地基BFS和DFS这两个遍历算法不是花架子后面最短路径、判断连通性、二分图检测、拓扑排序全都建立在它们之上。3.1 DFS一条路走到黑再回头换路深度优先搜索的思想很像走迷宫时“贴着一边走”从一个顶点出发沿一条边深入直到无法继续再回退到上一个分叉点换另一条路继续深入。DFS天然适合用递归实现因为递归自带回退。def dfs(graph, start, visitedNone): if visited is None: visited [False] * graph.n visited[start] True print(start, end ) for neighbor, _ in graph.neighbors(start): if not visited[neighbor]: dfs(graph, neighbor, visited)代码里最容易被忽略的是visited数组。如果不标记已访问顶点在带环的图里递归永远不会停下来会一直绕圈子直到栈溢出。我在初学阶段就踩过这个坑后来养成了一个习惯任何图遍历代码第一行永远先把“当前节点标记已访问”。DFS的时间复杂度是O(nm)空间复杂度最坏是O(n)。实际项目中检测图中是否存在环、计算连通分量、求无向图的割点都有DFS的身影。递归写法虽然好看但图深度很大时容易爆系统栈生产环境一般改成显式栈的迭代写法逻辑完全一致只是把系统栈换成了自己管理的列表。3.2 BFS一圈一圈往外扩擅长求最短跳数广度优先搜索的逻辑是“按层推进”。先访问起点再访问起点所有邻居再访问邻居的邻居像水面涟漪一样一圈圈扩散。from collections import deque def bfs(graph, start): visited [False] * graph.n queue deque([start]) visited[start] True while queue: v queue.popleft() print(v, end ) for neighbor, _ in graph.neighbors(v): if not visited[neighbor]: visited[neighbor] True queue.append(neighbor)注意BFS里的visited标记发生在入队时而不是出队时。如果出队时才标记同一个节点可能被多个邻居重复加入队列不仅效率低还可能出现重复处理的问题。这个细节很多新手会搞混我面试时也经常拿这个点考候选人。BFS在无权图上有一个天然优势从起点出发第一个到达某个顶点的路径就是经过边数最少的路径也就是最短跳数路径。社交网络里“找两个人之间隔了几层关系”、局域网广播消息本质都是BFS。3.3 两种遍历的适用边界与复杂度对比场景DFSBFS找所有可行路径合适不合适找无权图最短跳数不合适合适检测环合适可以找连通分量合适合适依赖递归/栈系统栈或显式栈队列空间复杂度O(n)O(n)实际工程项目里遍历很少单独出现更多是作为某个复杂算法的子过程。比如后面讲拓扑排序的Kahn算法本质就是BFS思想的变体而判断有向图是否有环DFS是更直接的工具。4. 最短路径Dijkstra算法为什么“贪心”能赢最短路径是图论里最经典的问题没有之一。导航给你规划路线网络路由选择下一跳节点物流系统计算送货成本全都逃不开最短路径。4.1 Dijkstra算法从起点不断“锁定”最近的顶点Dijkstra算法的核心思想是贪心每次从“未确定最短距离”的顶点里选一个当前距离最小的顶点把它加入“已确定”集合并用它去更新邻居的距离。假设有5个节点dist[0]0其余为无穷大。第一轮选择节点0更新它邻居的距离第二轮在未确定的节点里选dist最小者……每一轮都能锁定一个新的最小距离节点直到所有节点被锁定。import heapq def dijkstra(graph, start): INF float(inf) dist [INF] * graph.n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph.neighbors(u): nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return dist代码里用了优先队列每次弹出的都是当前距离最小的节点。if d dist[u]: continue这句叫“过期出队”非常重要。同一个节点可能被加入堆多次只有最新的一次距离才是有效的直接把没用的弹出。Dijkstra要求边的权重必须非负。原因很简单贪心成立的前提是“已经锁定的距离不可能再被别的路径更新”如果存在负权边后面某条路径反而可能让已锁定的距离变小前面的贪心就白做了。4.2 负权边的坑Bellman-Ford与SPFA如果要处理负权边标准做法是Bellman-Ford算法。它的思路是对所有边反复松弛最多松弛n-1轮因为最短路径不会包含正环或负环。如果第n轮还能松弛说明图里有负权回路问题本身无解。Bellman-Ford时间复杂度O(nm)图一大就跑不快。工程里通常用它的优化版本SPFA本质上是用队列管理“可能引起更新的节点”。SPFA在稀疏图上的实际效果非常快但最坏复杂度仍是指数级。这里提醒一句遇到负权边先判断有没有负环而不是直接套算法否则代码跑半天也得不到正确结果。如果只是判断负环可以用Bellman-Ford第n轮的检测也可以用DFS改造的判环方法不过实际中我更推荐前者逻辑简洁也不会踩爆栈。4.3 工程实践导航和路由的简化原理真实世界的导航不会直接用裸Dijkstra而是在它基础上加很多工程优化。最常见的是用A算法通过一个启发式函数优先探索离目的地更近的方向搜索空间比Dijkstra小很多。但A的前提是启发式函数设计得当否则找不到最优解。另一个优化思路是分层的路网。长距离导航先走高速网络再切到城市内部路网这就是热词里“分层图”的思路。大规模图计算时还会用多源最短路径、并行化的BFS变体不过这些是分布式图计算的范畴面试和考试核心还是Dijkstra本身。我在实际项目里用Dijkstra做过一次配送路径计算节点数几万用邻接表加堆优化单次计算在几十毫秒内完成。换成矩阵直接超时所以“邻接表堆优化Dijkstra”应该是每个开发者会背的标准模板。5. 最小生成树用最少成本连接所有节点最短路径解决“点到点”最小生成树解决“全连通”。一个通信网络要把n个城市用光缆连起来在保证所有城市互相可达的前提下让总造价最低这就是最小生成树问题。5.1 Prim算法从一个点慢慢“长”出整棵树Prim算法从任意顶点开始每次都选一条“连接树内顶点和树外顶点”的最小权边把树外顶点拉进树里直到所有顶点进树。直觉上是在不断扩张一个连通块有点像“结晶”过程。def prim(graph, start0): INF float(inf) mst [] dist [INF] * graph.n in_tree [False] * graph.n dist[start] 0 for _ in range(graph.n): u min((d, i) for i, d in enumerate(dist) if not in_tree[i] and d INF)[1] in_tree[u] True if dist[u] ! 0: mst.append(u) for v, w in graph.neighbors(u): if not in_tree[v] and w dist[v]: dist[v] w return mst注意代码里dist存的是“当前顶点到已构建树的最小边权”不是到起点的距离。这一点跟Dijkstra很容易混淆我写代码时吃过亏。两种算法结构确实很像但更新语义完全不同Dijkstra累加路径长度Prim取最小边权。5.2 Kruskal算法按边权从小到大排序合并Kruskal的思路更暴力先把所有边按权值从小到大排序然后一条条试。如果加入这条边后不形成环就保留如果形成环就丢弃。它天然适合稀疏图因为算法的瓶颈在排序上。判断是否成环需要用到并查集。并查集是Kruskal的隐藏主角它负责在近乎O(α(n))的时间内判断两个顶点是否属于同一集合以及把两个集合合并。没有并查集Kruskal的成环检测会搞得很低效。parent list(range(n)) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x def union(x, y): rx, ry find(x), find(y) if rx ! ry: parent[ry] rx按边权排序后从最小开始逐条尝试如果两个顶点不在同一个集合就合并边数达到n-1就可以提前终止。5.3 Prim还是Kruskal两个算法的真正区别对比维度PrimKruskal核心思想点扩展边排序复杂度O(n²)堆优化O(m log n)O(m log m)适合场景稠密图稀疏图辅助结构优先队列并查集编写难度中等中等实际考试代码题喜欢出Prim因为跟Dijkstra长得像好考察基础工程项目我更喜欢Kruskal因为只需要把边拉出来排序处理海量点但边稀疏的数据时更灵活。两种算法都能得到正确的最小生成树只要按图密度选就行。6. 拓扑排序与有向无环图依赖关系怎么排很多场景表面上和“路径”无关比如课程修读顺序、软件构建依赖、任务调度先后它们关心的是一个更重要的问题谁必须在谁前面。这些场景把任务建模成有向无环图用拓扑排序找出可行执行顺序。6.1 Kahn算法不断砍掉入度为0的节点Kahn算法的思路很容易理解先把所有入度为0的顶点入队代表“当前没有任何前置依赖可以最先执行”的任务不断出队把它所有邻居的入度减1邻居入度变成0时再入队最终如果输出的节点数不等于总节点数说明图里有环。from collections import deque def topological_sort(graph): indeg [0] * graph.n for u in range(graph.n): for v, _ in graph.neighbors(u): indeg[v] 1 queue deque([i for i in range(graph.n) if indeg[i] 0]) result [] while queue: u queue.popleft() result.append(u) for v, _ in graph.neighbors(u): indeg[v] - 1 if indeg[v] 0: queue.append(v) if len(result) ! graph.n: return None # 有环无法拓扑排序 return result我第一次写这个算法时忘记处理“有环”的情况结果输出铁丝对不上任务数。后来每次写完立刻加判断len(result) ! graph.n这个习惯帮我躲过了不少线上问题。6.2 判断有向图是否有环拓扑排序的隐藏价值有向图有没有环工程上是个很关键的问题。比如一个微服务调用链A调用B、B调用C、C又调用A就形成了循环依赖整个系统启动都会出问题。用拓扑排序检测环非常自然如果排完的节点数少于总节点数剩下的节点一定在环里。还可以用DFS配合访问状态数组状态0表示未访问1表示正在访问中2表示访问完毕DFS过程中如果遇到状态1的节点说明存在环。这个检测方式在死锁检测、依赖分析、定时任务调度检查里都很实用。我知道好几个定时任务调度系统启动前都会先跑一遍拓扑排序发现环就直接拒绝启动。6.3 工程案例课程表、构建系统与任务调度课程选修顺序是拓扑排序最经典的教材例子。比如学“数据库”之前必须先修“数据结构”学“数据结构”之前先修“程序设计”。把每门课当成顶点先修关系当成有向边拓扑排序输出的就是可行的选课顺序。软件构建系统也一样。一个大型项目拆成很多模块模块之间有编译依赖。构建工具拿到所有依赖关系后先用拓扑排序生成一个合法的编译顺序再用任务队列并发执行那些没有依赖冲突的模块。我实际参与过的项目里就是靠这个思路把编译时间从半小时压到了十分钟。任务调度系统里拓扑排序还被用来做优先级分层。入度为0的任务先跑跑完后释放依赖另一批任务入度变成0再跑。这种“先决条件”模式几乎是所有工作流引擎的核心骨架。7. 常见问题与踩坑实录这一章内容考试也考、工作也实际用但很多人容易在一些细节上翻车。把我自己踩过的和帮别人排查过的坑整理出来。7.1 邻接表忘记标记访问导致死循环最常见的Bug就是DFS里忘记把当前节点置为visited导致在有环图里无限递归。检查方法很简单所有遍历算法统一在“入队/入栈/进入递归前”标记而不是“处理时”标记。特别是BFS一定要在入队时标记否则同一个节点可能被加入队列多次结果程序跑得极慢还输出大量重复。7.2 Dijkstra遇到负权边还硬跑Dijkstra遇到负权边会给出错误结果但它不会报错。这个坑很隐蔽因为部分测试用例可能恰好通过了大型用例才暴露。我建议在初始化图时就明确边的权值范围如果输入可能有负数直接走Bellman-Ford或者SPFA别在Dijkstra上死磕。7.3 递归深度过大导致栈溢出DFS用递归实现时图深度可能超过Python默认递归限制。解决方式有三个用sys.setrecursionlimit调高限制改成显式栈迭代改用BFS。生产代码我一般直接用迭代把递归写法留在原型验证阶段。7.4 代码里INF定义不统一邻接矩阵里用float(inf)邻接表里如果边权很大用整数INF时取9999999两者混用时容易出错。建议统一用float(inf)或者全用同一个常量INF别为省那一点都不一致而踩数值比较的坑。问题现象可能原因处理办法BFS输出重复节点出队时才标记visited入队时立即标记Dijkstra结果错误存在负权边换Bellman-Ford/SPFADFS栈溢出递归深度过大改显式栈或BFS拓扑排序结果不完整图存在环先判环再排序邻接矩阵内存超限顶点数太大换邻接表图结构的知识点非常成体系前面这些内容之间也是环环相扣的存储结构决定算法写法遍历是各种路径算法的基础路径算法又反过来验证存储方案是否合理。我自己最深刻的体会是图这一章不能只背代码模板一定得自己在白纸上画几个小图亲手模拟一遍Dijkstra的更新过程、Prim的扩展过程、Kahn的删点过程把每个算法的“为什么”想明白代码自然就写得出来了。最后再分享一个技巧遇到新问题时先问自己能不能把它建模成图再问节点和边各代表什么。我曾经把一个文件依赖解析问题建模成有向图用拓扑排序一次性解决了循环依赖检测省掉了原先一堆if-else逻辑。数据结构里的图真正的价值不在于考试而在于它提供了一种“把复杂关系系统化”的思维方式这种思维方式一旦养成看什么系统都会带着一层图论的滤镜。
图数据结构核心算法全解析：从邻接表到Dijkstra与拓扑排序
数据结构学到“图”这一章才算真正撞上了算法的门槛。前面数组、链表、栈、队列、树核心都是处理“一对一”或“一对多”的关系脑子里还能画出清晰的层次结构但图完全不一样它允许任意两个节点之间都有连线能描述的关系复杂到吓人——导航软件里的路网、微信里的好友关系、编译器里的依赖解析、电商系统里的商品推荐背后全是图。我啃数据结构时最费劲的也是这一章。难不是因为它公式多而是需要同时具备“抽象建模”和“动手编码”两种能力你得先看懂一张图在表达什么再用邻接矩阵或邻接表把它装进内存最后还要把BFS、DFS、Dijkstra这些经典算法跑通。这篇文章我就站在这类“踩过坑、写过代码、也用图解决过实际问题”的角度把这章里最核心的东西重新捋一遍适合正在学数据结构的同学、准备考研408的选手以及工作中需要处理图关系的数据开发。1. 图到底是什么从“多对多”说起线性表和树之所以解决不了一些问题根源在于它们表达关系时都有“限制”。数组和链表是排队从头走到尾只能按顺序二叉树里每个节点最多挂两个子节点且一般不允许成环。图是唯一一种允许任意两个节点都产生直接联系的逻辑结构。1.1 线性、树、图数据关系三个层级你可以把这三者理解为三种不同复杂度的关系模型。单链表是一条铁链从head到尾节点只能按顺序走想回头就得从头再来。二叉树是一张组织结构图总经理下面有部门经理部门经理下面有组长每个人只有一个上级路径天然是单向、无环的。图则像现实中的地铁线路图你从任何一个站出发经过不同换乘都能到另一个站线路之间互相交叉还能绕圈子。图的形式化定义是图G由顶点集V和边集E组成记作G(V, E)。V是非空有穷集合E是连接V中顶点的边的有穷集合。这里注意树其实也是图的一种特例只是限制了“连通且无环”但课程和考试里一般单独讲树图这一章主要研究更一般、更自由的场景。1.2 有向、无向与加权关系本身也有差异边是否带方向是图的一个重要分类维度。如果边没有方向A和B之间存在一条边那么从A能到B从B也能到A这叫无向图适合描述“邻居”“朋友”“网络链路”这类天然双向的关系。如果边带方向从A能走到B除非存在一条B到A的边否则回不来这叫有向图。微博关注关系是典型你关注了一个大V但大V不一定关注你这种不对称关系必须用有向图。再看权重。每条边带上数值就是带权图。权重可以表示两个节点的距离、费用、时间或流量。不带权的图叫无权图默认每条边的权重都是1。最短路径问题里权重就是决定“最优”的关键依据没有权重就只能按“跳数最少”来算。1.3 稠密与稀疏直接决定存储方案的选择这里有两个必须搞清楚的概念它们是后面选存储结构、估算法复杂度的重要依据。第一个是边的数量级。n个顶点的无向图最多有n(n-1)/2条边。什么时候算稠密、什么时候算稀疏没有绝对标准按我的经验边的数量接近n的平方量级就是稠密接近n量级就是稀疏。城市道路网属于稀疏图而一个班级里所有学生之间都存在联系的关系网就比较稠密。第二个是连通分量。无向图里如果任意两个顶点都互相可达称为连通图否则就是非连通图它的极大连通子图叫连通分量。有向图里还要区分强连通和弱连通。这些名词在考试里出现频率很高建议自己画几个例子验证一遍光背定义容易混。2. 存储结构选型邻接矩阵还是邻接表图怎么装进计算机经典方案就两个邻接矩阵和邻接表。这一节说清楚它们在内存中是什么样的、代码怎么实现、什么场景选谁。2.1 邻接矩阵O(1)查边的代价是O(n²)空间邻接矩阵用二维数组存储。a[i][j]1表示顶点i到j有边0表示没有若是带权图就用具体权值没有边则用无穷大表示。用Python实现非常直观class GraphMatrix: def __init__(self, n, directedFalse): INF float(inf) self.n n self.directed directed self.matrix [[INF] * n for _ in range(n)] for i in range(n): self.matrix[i][i] 0 def add_edge(self, u, v, weight1): self.matrix[u][v] weight if not self.directed: self.matrix[v][u] weight注意我初始化时用了INF而不是0长度判断“没有边”时不再用0而用无穷大。这样的好处是后面跑最短路径算法时直接取min就能继续写不需要额外判断。用0表示无边只适合纯连通性判断遇到带权图一定要改用无穷大。邻接矩阵最大的优势是判断两点之间是否有边只需O(1)时间代码写起来逻辑特别直。代价是空间复杂度O(n²)顶点数到一万以上就会爆内存。我平时在本地跑实验节点超过5000就基本不考虑矩阵了。2.2 邻接表空间省了查边变慢了一点邻接表是“数组链表”的组合。每个顶点对应一个链表链表里存的是与该顶点相连的邻居以及边权。稀疏图里所有链表长度之和约等于边数m空间复杂度O(nm)比矩阵省得多。Python实现用list of list就够了class GraphList: def __init__(self, n, directedFalse): self.n n self.directed directed self.adj [[] for _ in range(n)] def add_edge(self, u, v, weight1): self.adj[u].append((v, weight)) if not self.directed: self.adj[v].append((u, weight)) def neighbors(self, u): return self.adj[u]邻接表里判断u和v之间是否有边需要遍历u的邻接链表最坏O(度)。实际算法中我们经常做的是“从某个点出发看它的所有邻居”这种场景邻接表反而是最自然的形态遍历、搜索、路径算法基本都优先用邻接表。2.3 选型建议别无脑跟风看场景挑对比维度邻接矩阵邻接表空间复杂度O(n²)O(nm)判断u、v是否有边O(1)O(度)遍历u的所有邻居O(n)O(度)适合场景稠密图、频繁查边稀疏图、大规模图实现难度低中等我自己的习惯是节点数在1000以内、边比较密集时用矩阵写起来省心节点数大、边稀疏时用邻接表内存压力小。考试写算法题我推荐邻接表因为考研代码题给的输入规模一般都不大邻接表又通用不会因为题目没说明图的密度而翻车。3. 遍历是通往一切图算法的地基BFS和DFS这两个遍历算法不是花架子后面最短路径、判断连通性、二分图检测、拓扑排序全都建立在它们之上。3.1 DFS一条路走到黑再回头换路深度优先搜索的思想很像走迷宫时“贴着一边走”从一个顶点出发沿一条边深入直到无法继续再回退到上一个分叉点换另一条路继续深入。DFS天然适合用递归实现因为递归自带回退。def dfs(graph, start, visitedNone): if visited is None: visited [False] * graph.n visited[start] True print(start, end ) for neighbor, _ in graph.neighbors(start): if not visited[neighbor]: dfs(graph, neighbor, visited)代码里最容易被忽略的是visited数组。如果不标记已访问顶点在带环的图里递归永远不会停下来会一直绕圈子直到栈溢出。我在初学阶段就踩过这个坑后来养成了一个习惯任何图遍历代码第一行永远先把“当前节点标记已访问”。DFS的时间复杂度是O(nm)空间复杂度最坏是O(n)。实际项目中检测图中是否存在环、计算连通分量、求无向图的割点都有DFS的身影。递归写法虽然好看但图深度很大时容易爆系统栈生产环境一般改成显式栈的迭代写法逻辑完全一致只是把系统栈换成了自己管理的列表。3.2 BFS一圈一圈往外扩擅长求最短跳数广度优先搜索的逻辑是“按层推进”。先访问起点再访问起点所有邻居再访问邻居的邻居像水面涟漪一样一圈圈扩散。from collections import deque def bfs(graph, start): visited [False] * graph.n queue deque([start]) visited[start] True while queue: v queue.popleft() print(v, end ) for neighbor, _ in graph.neighbors(v): if not visited[neighbor]: visited[neighbor] True queue.append(neighbor)注意BFS里的visited标记发生在入队时而不是出队时。如果出队时才标记同一个节点可能被多个邻居重复加入队列不仅效率低还可能出现重复处理的问题。这个细节很多新手会搞混我面试时也经常拿这个点考候选人。BFS在无权图上有一个天然优势从起点出发第一个到达某个顶点的路径就是经过边数最少的路径也就是最短跳数路径。社交网络里“找两个人之间隔了几层关系”、局域网广播消息本质都是BFS。3.3 两种遍历的适用边界与复杂度对比场景DFSBFS找所有可行路径合适不合适找无权图最短跳数不合适合适检测环合适可以找连通分量合适合适依赖递归/栈系统栈或显式栈队列空间复杂度O(n)O(n)实际工程项目里遍历很少单独出现更多是作为某个复杂算法的子过程。比如后面讲拓扑排序的Kahn算法本质就是BFS思想的变体而判断有向图是否有环DFS是更直接的工具。4. 最短路径Dijkstra算法为什么“贪心”能赢最短路径是图论里最经典的问题没有之一。导航给你规划路线网络路由选择下一跳节点物流系统计算送货成本全都逃不开最短路径。4.1 Dijkstra算法从起点不断“锁定”最近的顶点Dijkstra算法的核心思想是贪心每次从“未确定最短距离”的顶点里选一个当前距离最小的顶点把它加入“已确定”集合并用它去更新邻居的距离。假设有5个节点dist[0]0其余为无穷大。第一轮选择节点0更新它邻居的距离第二轮在未确定的节点里选dist最小者……每一轮都能锁定一个新的最小距离节点直到所有节点被锁定。import heapq def dijkstra(graph, start): INF float(inf) dist [INF] * graph.n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph.neighbors(u): nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return dist代码里用了优先队列每次弹出的都是当前距离最小的节点。if d dist[u]: continue这句叫“过期出队”非常重要。同一个节点可能被加入堆多次只有最新的一次距离才是有效的直接把没用的弹出。Dijkstra要求边的权重必须非负。原因很简单贪心成立的前提是“已经锁定的距离不可能再被别的路径更新”如果存在负权边后面某条路径反而可能让已锁定的距离变小前面的贪心就白做了。4.2 负权边的坑Bellman-Ford与SPFA如果要处理负权边标准做法是Bellman-Ford算法。它的思路是对所有边反复松弛最多松弛n-1轮因为最短路径不会包含正环或负环。如果第n轮还能松弛说明图里有负权回路问题本身无解。Bellman-Ford时间复杂度O(nm)图一大就跑不快。工程里通常用它的优化版本SPFA本质上是用队列管理“可能引起更新的节点”。SPFA在稀疏图上的实际效果非常快但最坏复杂度仍是指数级。这里提醒一句遇到负权边先判断有没有负环而不是直接套算法否则代码跑半天也得不到正确结果。如果只是判断负环可以用Bellman-Ford第n轮的检测也可以用DFS改造的判环方法不过实际中我更推荐前者逻辑简洁也不会踩爆栈。4.3 工程实践导航和路由的简化原理真实世界的导航不会直接用裸Dijkstra而是在它基础上加很多工程优化。最常见的是用A算法通过一个启发式函数优先探索离目的地更近的方向搜索空间比Dijkstra小很多。但A的前提是启发式函数设计得当否则找不到最优解。另一个优化思路是分层的路网。长距离导航先走高速网络再切到城市内部路网这就是热词里“分层图”的思路。大规模图计算时还会用多源最短路径、并行化的BFS变体不过这些是分布式图计算的范畴面试和考试核心还是Dijkstra本身。我在实际项目里用Dijkstra做过一次配送路径计算节点数几万用邻接表加堆优化单次计算在几十毫秒内完成。换成矩阵直接超时所以“邻接表堆优化Dijkstra”应该是每个开发者会背的标准模板。5. 最小生成树用最少成本连接所有节点最短路径解决“点到点”最小生成树解决“全连通”。一个通信网络要把n个城市用光缆连起来在保证所有城市互相可达的前提下让总造价最低这就是最小生成树问题。5.1 Prim算法从一个点慢慢“长”出整棵树Prim算法从任意顶点开始每次都选一条“连接树内顶点和树外顶点”的最小权边把树外顶点拉进树里直到所有顶点进树。直觉上是在不断扩张一个连通块有点像“结晶”过程。def prim(graph, start0): INF float(inf) mst [] dist [INF] * graph.n in_tree [False] * graph.n dist[start] 0 for _ in range(graph.n): u min((d, i) for i, d in enumerate(dist) if not in_tree[i] and d INF)[1] in_tree[u] True if dist[u] ! 0: mst.append(u) for v, w in graph.neighbors(u): if not in_tree[v] and w dist[v]: dist[v] w return mst注意代码里dist存的是“当前顶点到已构建树的最小边权”不是到起点的距离。这一点跟Dijkstra很容易混淆我写代码时吃过亏。两种算法结构确实很像但更新语义完全不同Dijkstra累加路径长度Prim取最小边权。5.2 Kruskal算法按边权从小到大排序合并Kruskal的思路更暴力先把所有边按权值从小到大排序然后一条条试。如果加入这条边后不形成环就保留如果形成环就丢弃。它天然适合稀疏图因为算法的瓶颈在排序上。判断是否成环需要用到并查集。并查集是Kruskal的隐藏主角它负责在近乎O(α(n))的时间内判断两个顶点是否属于同一集合以及把两个集合合并。没有并查集Kruskal的成环检测会搞得很低效。parent list(range(n)) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x def union(x, y): rx, ry find(x), find(y) if rx ! ry: parent[ry] rx按边权排序后从最小开始逐条尝试如果两个顶点不在同一个集合就合并边数达到n-1就可以提前终止。5.3 Prim还是Kruskal两个算法的真正区别对比维度PrimKruskal核心思想点扩展边排序复杂度O(n²)堆优化O(m log n)O(m log m)适合场景稠密图稀疏图辅助结构优先队列并查集编写难度中等中等实际考试代码题喜欢出Prim因为跟Dijkstra长得像好考察基础工程项目我更喜欢Kruskal因为只需要把边拉出来排序处理海量点但边稀疏的数据时更灵活。两种算法都能得到正确的最小生成树只要按图密度选就行。6. 拓扑排序与有向无环图依赖关系怎么排很多场景表面上和“路径”无关比如课程修读顺序、软件构建依赖、任务调度先后它们关心的是一个更重要的问题谁必须在谁前面。这些场景把任务建模成有向无环图用拓扑排序找出可行执行顺序。6.1 Kahn算法不断砍掉入度为0的节点Kahn算法的思路很容易理解先把所有入度为0的顶点入队代表“当前没有任何前置依赖可以最先执行”的任务不断出队把它所有邻居的入度减1邻居入度变成0时再入队最终如果输出的节点数不等于总节点数说明图里有环。from collections import deque def topological_sort(graph): indeg [0] * graph.n for u in range(graph.n): for v, _ in graph.neighbors(u): indeg[v] 1 queue deque([i for i in range(graph.n) if indeg[i] 0]) result [] while queue: u queue.popleft() result.append(u) for v, _ in graph.neighbors(u): indeg[v] - 1 if indeg[v] 0: queue.append(v) if len(result) ! graph.n: return None # 有环无法拓扑排序 return result我第一次写这个算法时忘记处理“有环”的情况结果输出铁丝对不上任务数。后来每次写完立刻加判断len(result) ! graph.n这个习惯帮我躲过了不少线上问题。6.2 判断有向图是否有环拓扑排序的隐藏价值有向图有没有环工程上是个很关键的问题。比如一个微服务调用链A调用B、B调用C、C又调用A就形成了循环依赖整个系统启动都会出问题。用拓扑排序检测环非常自然如果排完的节点数少于总节点数剩下的节点一定在环里。还可以用DFS配合访问状态数组状态0表示未访问1表示正在访问中2表示访问完毕DFS过程中如果遇到状态1的节点说明存在环。这个检测方式在死锁检测、依赖分析、定时任务调度检查里都很实用。我知道好几个定时任务调度系统启动前都会先跑一遍拓扑排序发现环就直接拒绝启动。6.3 工程案例课程表、构建系统与任务调度课程选修顺序是拓扑排序最经典的教材例子。比如学“数据库”之前必须先修“数据结构”学“数据结构”之前先修“程序设计”。把每门课当成顶点先修关系当成有向边拓扑排序输出的就是可行的选课顺序。软件构建系统也一样。一个大型项目拆成很多模块模块之间有编译依赖。构建工具拿到所有依赖关系后先用拓扑排序生成一个合法的编译顺序再用任务队列并发执行那些没有依赖冲突的模块。我实际参与过的项目里就是靠这个思路把编译时间从半小时压到了十分钟。任务调度系统里拓扑排序还被用来做优先级分层。入度为0的任务先跑跑完后释放依赖另一批任务入度变成0再跑。这种“先决条件”模式几乎是所有工作流引擎的核心骨架。7. 常见问题与踩坑实录这一章内容考试也考、工作也实际用但很多人容易在一些细节上翻车。把我自己踩过的和帮别人排查过的坑整理出来。7.1 邻接表忘记标记访问导致死循环最常见的Bug就是DFS里忘记把当前节点置为visited导致在有环图里无限递归。检查方法很简单所有遍历算法统一在“入队/入栈/进入递归前”标记而不是“处理时”标记。特别是BFS一定要在入队时标记否则同一个节点可能被加入队列多次结果程序跑得极慢还输出大量重复。7.2 Dijkstra遇到负权边还硬跑Dijkstra遇到负权边会给出错误结果但它不会报错。这个坑很隐蔽因为部分测试用例可能恰好通过了大型用例才暴露。我建议在初始化图时就明确边的权值范围如果输入可能有负数直接走Bellman-Ford或者SPFA别在Dijkstra上死磕。7.3 递归深度过大导致栈溢出DFS用递归实现时图深度可能超过Python默认递归限制。解决方式有三个用sys.setrecursionlimit调高限制改成显式栈迭代改用BFS。生产代码我一般直接用迭代把递归写法留在原型验证阶段。7.4 代码里INF定义不统一邻接矩阵里用float(inf)邻接表里如果边权很大用整数INF时取9999999两者混用时容易出错。建议统一用float(inf)或者全用同一个常量INF别为省那一点都不一致而踩数值比较的坑。问题现象可能原因处理办法BFS输出重复节点出队时才标记visited入队时立即标记Dijkstra结果错误存在负权边换Bellman-Ford/SPFADFS栈溢出递归深度过大改显式栈或BFS拓扑排序结果不完整图存在环先判环再排序邻接矩阵内存超限顶点数太大换邻接表图结构的知识点非常成体系前面这些内容之间也是环环相扣的存储结构决定算法写法遍历是各种路径算法的基础路径算法又反过来验证存储方案是否合理。我自己最深刻的体会是图这一章不能只背代码模板一定得自己在白纸上画几个小图亲手模拟一遍Dijkstra的更新过程、Prim的扩展过程、Kahn的删点过程把每个算法的“为什么”想明白代码自然就写得出来了。最后再分享一个技巧遇到新问题时先问自己能不能把它建模成图再问节点和边各代表什么。我曾经把一个文件依赖解析问题建模成有向图用拓扑排序一次性解决了循环依赖检测省掉了原先一堆if-else逻辑。数据结构里的图真正的价值不在于考试而在于它提供了一种“把复杂关系系统化”的思维方式这种思维方式一旦养成看什么系统都会带着一层图论的滤镜。
