学数据结构的人十有八九觉得“图”是最后一座山。数组是排队买奶茶链表是演唱会手拉手树是公司组织架构可到了图这里所有规则都松绑了任意两个节点都能相连方向可走可不走边上还能挂数字。我第一次学的时候也很懵后来发现图恰恰是所有数据结构里最贴近真实世界的一种地铁换乘、社交好友、路由跳数、任务依赖统统可以用图建模。这篇内容不搞高深推导从一个普通开发者的视角把图的基础概念、存储方式、几种核心算法以及实际踩坑经验一次讲透适合正在啃教材的学生、准备算法面试的求职者以及想用图建模但一直没下手的工程师。1. 图到底是什么先建立建模思维1.1 从“树不够用”说起树解决的是层次问题但现实里大多关系是任意的。拿微信好友举例A和B是好友B和C也是A和C之间可能有直接关系也可能没有这种关系没法用一棵树表达因为一个人可以有多个父节点。图把这个问题抽象得非常干净“顶点”是实体“边”是关系。每条边还可以带权表示距离、成本、容量等等。图的正式定义是 G (V, E)。V 是有限非空的顶点集合E 是顶点对构成的边集合。边没有方向叫无向图有方向叫有向图边上带权值叫带权图。处理图问题的第一步不是急着背算法而是想清楚用无向还是有向顶点代表什么边代表什么权值又代表什么。我在一个模拟项目X里做过订单流转建模订单、仓库、配送节点之间的依赖关系画出来就是一张有向带权图顶点是业务状态边是转移条件权值是耗时成本。建模一旦清楚后面用哪个算法几乎是顺理成章的事。1.2 图的专业术语一轮速通图论术语看着多其实常用就那几个。这里整理成速查表方便你随时翻。术语含义一句话记忆顶点的度关联顶点的边数无向图中一条边贡献两度入度 / 出度有向图中进入 / 射出的边数入度加出度等于总度路径顶点序列相邻顶点之间有边连续不断线回路 / 环起点和终点相同的路径绕一圈回到原点连通图任意两个顶点之间都有路径无向图没有孤岛强连通图任意两个顶点互相可达有向图的双向通路连通分量极大连通子图图中每个“岛屿”完全图任意两个顶点之间都有边无向图 n(n-1)/2 条边稀疏图 / 稠密图边数相对顶点数平方的比例稀疏省钱用邻接表这些词不需要刻意背做题时会反复出现。比如强连通分量在社交推荐、程序依赖分析里很常见连通分量则是“图里有几块独立区域”的直观答案。把这几个概念放在一起理解后面看算法会轻松很多。2. 存储结构邻接矩阵和邻接表到底怎么选2.1 邻接矩阵直观粗暴但空间容易爆邻接矩阵用一个二维数组存边。matrix[i][j] 1表示顶点 i 到顶点 j 有边带权图就存权值没有边就存一个很大的数 INF。判断两个顶点是否相邻查一次数组就行时间复杂度 O(1)这是它最大的优势。但代价是空间。比如 10000 个顶点的稀疏图用 int 矩阵要开 1 亿个格子约 400MB普通机器直接扛不住。而且想遍历某个顶点的所有邻接点必须扫一整行复杂度是 O(V)完全浪费。所以邻接矩阵只适合稠密图或者顶点规模很小的场景。我见过有人图省事在小规模题里用矩阵确实干净利落但一旦顶点到了几千矩阵基本被淘汰。2.2 邻接表工程里最常见的方案邻接表的思路是每个顶点挂一条链表或者一个数组里面存它能到达的邻居以及边权。空间是 O(VE)稀疏图省下大把内存。查询某个顶点的邻居只需要遍历它的链表平均成本很低。C 可以写成vectorvectorpairint,intPython 用defaultdict(list)最顺手。from collections import defaultdict graph defaultdict(list) graph[0].append((1, 5)) # 顶点0到顶点1权值5 graph[1].append((2, 3)) graph[0].append((2, 7))无向图建表时记得每条边加两次比如graph[0].append((1,5))和graph[1].append((0,5))。我早期写程序经常漏掉对称的这一半导致遍历结果少一大片排查半天才发现是建图的问题。邻接表唯一的缺点是判断任意两个顶点是否相邻不太方便得遍历一遍邻居链表。工程上绝大多数图都是稀疏的所以邻接表是首选。2.3 两个偏冷门但值得了解的存储结构十字链表针对有向图把出边和入边都链起来找顶点的前驱和后继都很方便。邻接多重表针对无向图每条边只存一份两个顶点共用避免邻接表存两次带来的更新麻烦。工程里直接手写这两个结构的场景不多但理解它们能帮你加深对“反向边”“双向关系”的感知。这四个结构可以简单对比一下存储结构空间判断两点相邻遍历邻居适用场景邻接矩阵O(V^2)O(1)O(V)稠密图、小规模图邻接表O(VE)O(degree)O(degree)稀疏图、工程主力十字链表O(VE)O(degree)O(degree)有向图双向查询邻接多重表O(VE)O(degree)O(degree)无向图频繁改边某跨平台系统的关系存储最终选了邻接表加反向索引因为业务上经常要做双向查询单纯用十字链表反而维护复杂。存储结构的选择永远跟着业务需求走没有绝对的好坏。3. DFS 和 BFS图遍历的两个引擎3.1 深度优先搜索一条路走到黑碰壁再回头DFS 的思路和树的先序遍历很像从起点出发沿着一条边一直访问下一个顶点直到没有新邻居再退回上一个岔路口继续。图的问题在于有环必须用 visited 数组标记已经访问过的顶点不然会死循环。visited [False] * n def dfs(graph, v): visited[v] True # 在这里处理当前顶点 for nxt, _ in graph[v]: if not visited[nxt]: dfs(graph, nxt) # 图可能不连通需要遍历所有起点 for i in range(n): if not visited[i]: dfs(graph, i)DFS 的递归实现写起来很爽但图特别大或者深度很深时递归栈容易爆。解决方案是改成显式栈自己压节点。DFS 能做的事很多统计连通分量、检测环、拓扑排序、求迷宫路径。如果题目要求“找到一条路径”大概率优先想 DFS。3.2 广度优先搜索一圈一圈往外扩BFS 用队列实现从起点出发先访问所有邻居再访问邻居的邻居像水面涟漪一样层层扩散。它最大的优势是在无权图里第一次扩散到的层数就是最短路径长度。from collections import deque def bfs(graph, start): visited [False] * n q deque([start]) visited[start] True dist 0 while q: for _ in range(len(q)): v q.popleft() # 在这里处理当前顶点 for nxt, _ in graph[v]: if not visited[nxt]: visited[nxt] True q.append(nxt) dist 1这里的for _ in range(len(q))是按层处理的经典写法。我早期写 BFS 经常忽略分层结果距离怎么算都不对后来固定用这个模板遇到“最短步数”“扩散轮数”的题直接套。两个遍历算法各有主场维度DFSBFS底层结构栈递归队列空间消耗O(V) 最深路径O(V) 最宽层无权图最短路径不适用适用环路检测三色标记方便Kahn 拓扑方便拓扑排序后序逆序Kahn 算法方便典型应用连通性、回溯、染色分层、最短步数4. 最短路径导航和路由的底层逻辑4.1 Dijkstra当贪心遇上最短路径Dijkstra 解决的是单源最短路径问题已经知道起点求它到所有顶点的最短距离。核心思路很直白每次都从未确定的顶点中选距离最小的那个用它的出边去松弛邻居。import heapq def dijkstra(graph, s): INF 10**18 dist [INF] * n dist[s] 0 pq [(0, s)] 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堆优化后复杂度是 O((VE)logV)是目前单源非负权场景下的主力算法。为什么它不能处理负权边因为一旦某个顶点的距离被标记为“确定”如果后面出现一条负边让距离变得更小之前的贪心决策就失效了。面试官很喜欢追问这一点一句话回答贪心要求局部最优能推出全局最优负权边破坏了这一前提。4.2 Floyd-Warshall三重循环解决任意两点最短路如果要求图上任意两个顶点之间的最短路径顶点规模又不大比如 500 以内Floyd 是最省脑子的方案。这是一个动态规划状态是“只允许经过前 k 个顶点作为中转”时的最短路。INF 10**18 dist [[INF] * n for _ in range(n)] for i in range(n): dist[i][i] 0 # 初始化边权dist[u][v] w 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]注意 k 循环必须放在最外层写反了结果全错。Floyd 能处理负权边但不能有负环否则最短路会无限变小。实际工程中如果 V 到了几千三重循环 O(V^3) 基本跑不动所以 Floyd 更多出现在题目里“V 很小”的语境下。4.3 工程上怎么选最短路径算法场景推荐算法复杂度单源边权非负Dijkstra 堆O((VE)logV)单源存在负权边Bellman-Ford / SPFAO(VE) / 通常更快任意两点V 小Floyd-WarshallO(V^3)大规模稀疏图优先用现成图库视实现而定某地图类 Demo 里顶点数量在几千级别Dijkstra 毫秒级跑完Floyd 反而吃力。所以我的建议永远是先看数据规模再选算法不要因为某个算法学起来简单就无脑用。5. 最小生成树花最少的钱把网铺满5.1 问题到底长什么样通信公司要把 n 个小区用光缆连通每两个小区之间施工成本不同怎么选线路才能让总成本最低这就是最小生成树问题在连通无向带权图里选 n-1 条边让所有顶点连通并且总权值最小。最小生成树可能有多个但总权值唯一。它解决的场景包括网络铺设、电路布线、聚类分析等本质都是“用最少的成本把点连起来”。5.2 Prim 算法从顶点往外长Prim 的思路是从任意一个顶点出发维护一个已经连通的点集每一步从“连接点集和外部顶点”的所有边里挑一条权值最小的把对应的新顶点纳入点集。它和 Dijkstra 长得非常像差别在于Dijkstra 更新的是到起点的总距离Prim 更新的是到当前点集的最近距离。朴素写法 O(V^2)堆优化后 O((VE)logV)适合稠密图。5.3 Kruskal 算法从边往中间剪Kruskal 的思路更简单把所有边按权值从小到大排序依次尝试如果边的两个端点还没有被连通就选它并用并查集把两端合并。选够 n-1 条边就停。edges.sort(keylambda x: x[2]) # 每条边 (u, v, w) parent list(range(n)) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x mst_weight 0 cnt 0 for u, v, w in edges: ru, rv find(u), find(v) if ru ! rv: parent[ru] rv mst_weight w cnt 1 if cnt n - 1: break两个算法怎么选项目PrimKruskal扩展方式点扩张边合并核心依赖堆 / 朴素数组并查集典型复杂度O((VE)logV)O(ElogE)适合场景稠密图稀疏图实现难度中等简单前提是熟练并查集工程里顶点少但边很密的场景 Prim 更稳顶点多但边稀疏的场景 Kruskal 更省。某网络规划项目里最终选 Kruskal因为边数不过几万排序后一次扫描逻辑非常直白。6. 拓扑排序与关键路径有向无环图的价值6.1 Kahn 算法把依赖关系排成有序列表工程里的依赖关系很多都是有向无环图DAG课程前置关系、包依赖、任务编排。拓扑排序要做的是输出一个线性顺序保证每条边的起点都在终点前面。Kahn 算法用入度来驱动统计所有顶点的入度。入度为 0 的顶点入队这些顶点没有前置依赖可以先处理。出队时把它所有出边邻居的入度减 1如果邻居入度变成 0就入队。如果最终出队的顶点数小于 V说明图里有环。from collections import deque, defaultdict 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]) order [] while q: u q.popleft() order.append(u) for v in graph[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) if len(order) ! n: print(图中存在环) else: print(order)拓扑排序的工程价值很高。有一次我做模拟项目X的发布流程设计构建任务之间有一堆先后约束拓扑排序直接把构建顺序输出来了比手工排流程靠谱得多。6.2 关键路径项目最短工期怎么算如果边表示活动耗时顶点表示事件这种 AOE 网里决定整个项目工期的就是最长路径也叫关键路径。计算过程可以拆成四步按拓扑序求每个事件的最早发生时间 ve。按逆拓扑序求每个事件的最晚发生时间 vl。对每条边活动最早开始时间 e ve[起点]最晚开始时间 l vl[终点] - 边权。l - e 0 的边就是关键活动连起来就是关键路径。这个算法容易写错的地方是逆拓扑序没处理好。我的习惯是 Kahn 算法里已经把 order 收集好了把 order 反转就是逆拓扑序一步到位不需要再单独 DFS 一遍。关键路径不一定只有一条每个有 0 余量的活动都值得关注因为任何一个被拖住整个项目都要延期。7. 实战高频问题与避坑手册7.1 三类必会问题连通、环、二分图连通分量个数是最基础的图问题DFS 或 BFS 遍历一遍统计几轮循环就是几个分量。很多题会问“最少加几条边让整张图连通”答案就是分量数减 1。环路检测要分场景。无向图用并查集在加入一条边时如果两个端点已经在同一集合里说明有环。有向图用拓扑排序或 DFS 三色标记法我个人更推荐拓扑排序因为它在检测环的同时还能给出依赖顺序。二分图判定用染色法BFS 或 DFS 给顶点交替染两种颜色一旦发现相邻顶点同色就不是二分图。这个套路在“能否把矛盾双方分成两组”的题目里经常出现。7.2 我踩过的几个典型坑现象原因处理方式遍历少了一部分顶点没处理非连通图外层 for 循环遍历所有起点距离被算小Dijkstra 用了负权边换 Bellman-Ford最短路计算溢出INF INF 爆范围用足够大的 INF如 10^18递归 DFS 爆栈图太大或深度太深改显式栈邻接表出现重边输入数据没去重建图时用 set 或只保留最小权并查集判断出错没初始化 parent记得parent[i] iFloyd 结果全 INFk 写到了内层k 必须放最外层还有一个工程技巧带权图如果同一对顶点有多条边很多题不会明说但实际数据里就是会有建图时最好只保留最小权值否则后面最短路径算法会给出错误结果。我已经在这种隐蔽的地方栽过好几次。7.3 需要常备的算法模板清单面试或考试前如果时间紧至少要把这几段代码写顺建图邻接矩阵和邻接表、DFS、BFS、Dijkstra、并查集加 Kruskal、拓扑排序、染色法。我自己的习惯是把这些模板按固定注释格式存下来考场上先写骨架再补细节。模板的作用不是让你背答案而是减少低级错误让你把精力留给真正需要思考的建模部分。8. 写在最后我对图的实践体会图这块内容我反复学了不止一遍最大的体会是图的算法并不多难的是把现实问题翻译成图。拿到任何题目先问自己三句话顶点是谁边是什么要算什么这三句话想清楚了后面的算法几乎是机械调用。早期我学图时总想一口气背完所有算法结果遇到变形题还是懵后来改成“先建模、再套模板”正确率明显上来了。再分享一个小技巧遇到图相关的问题先在纸上画一个小例子手动跑一遍期望答案再动手写代码。画出来之后很多边界情况会自己冒出来。图这种数据结构和数组、树都不一样它没有天然的“从头开始”所以写代码时多想想非连通、空图、单顶点这些极端情况。把这些细节都稳住图就没有传说中那么可怕。