数据结构里最容易被忽略、却又最值钱的部分我觉得就是图。链表、栈、队列说到底还是线性的思维树好歹是层次关系但到了图整个局面就变成了一张网。很多人在这一步开始犯迷糊我能理解——图是数据结构和算法从“理解”走向“运用”的分水岭也是王道408、校招笔试、还甚至后面图计算、图神经网络这些方向的地基。今天我把“数据结构之图”这块掰开揉碎讲一遍从概念、存储、遍历到最小生成树、最短路径、拓扑排序再到考研和实际工程里怎么考、怎么用尽量用一次能听懂的思路给你盘完。如果你正在准备数据结构期末考试、408考研复习或者刚开始接触算法题被各种图论题折磨这篇文章就是照着“踩坑实录”写的。很多细节是我自己在手写代码和跑实验时反复栽过跟头才总结出来的常规教材上不会写这么细。1. 先把图的“长相”看清楚概念与建模1.1 什么是图为什么它比树难图Graph是由顶点集合 V 和边集合 E 组成的一种数据结构记作 G(V,E)。听起来跟树好像差不多但树有一个硬性约束任意两个节点之间只能有一条通路。图没有这个限制它允许任意两个顶点之间建立连接甚至允许一条边从某个点绕一大圈再回到原来的点。这种“任意连接”的特性导致思维方式的彻底改变。处理树的时候我们可以找到唯一的根然后一层一层往下走处理图的时候没有天然的“上层”和“下层”你从任何一个顶点出发都可以进入这个结构而且同一个顶点可能通过多条路径到达这就得靠额外的标记去避免重复访问。我经常把图和树的关系类比成交通网和家族谱家族谱一定是分代、有固定层级子女不会指向祖先但城市的地铁线路图就不一样了站和站之间互相连接你从 A 站出发可以绕一圈又回到 A 站。理解了这类生活场景再去看图的定义就不会觉得抽象了。1.2 图的几个基本术语顶点、边、度、路径、连通分量学习图第一步就是把术语搞明白因为后面所有算法都建立在术语之上。顶点Vertex图里的基本单位也可以叫节点比如地铁站、网络里的路由器、社交软件里的用户。边Edge两个顶点之间的连接关系表示“有关系”或者“能到达”。有向图与无向图有向图的边带方向A→B 和 B→A 是两条不同的边无向图的边不带方向A-B 和 B-A 是同一件事。度Degree无向图中某顶点关联的边数叫度。有向图里要分入度指向该顶点的边数和出度从该顶点指出的边数。路径与路径长度路径是由顶点和边组成的序列路径长度通常指经过的边数带权图中则可能指权重之和。连通与连通分量无向图中如果任意两个顶点之间都有路径则称图连通非连通图会被拆成多个连通分量。有向图中还有强连通分量的概念指的是任意两个顶点互相可达的最大子图。这些术语不好好记后面写算法时会产生一堆细节问题。比如“记录每个顶点的入度”是拓扑排序的关键你连入度是什么都没想明白代码根本无从下手。1.3 带权图与有向图从社交关系到地图导航图的威力在于它能映射现实世界的关系。把用户当成顶点把“关注”当成有向边这就是社交网络图把路口当成顶点把道路当成带权边权重是距离或耗时这就是地图导航的底层模型。之所以强调建模是因为同一个数据你的建图方式不同后续算法完全不同。比如地铁换乘问题最自然的建模就是把每个站当成顶点相邻两站之间连一条边边权为运行时间但如果加上换乘步行时间就得把“换乘”也建模成一种特殊的边或者扩展成多层图。具体面试题里经常看到“分层图”的思想本质上就是用不同的层表示不同的状态这是热点也是难点。我在实际做图计算项目时也常常因为建图方式不贴合业务场景而返工所以建议你在动笔写算法之前先用十分钟把图的模型设计清楚这比优化代码更值得。2. 图的存储结构选型邻接矩阵还是邻接表2.1 邻接矩阵简单直观但内存开销大邻接矩阵是用一个二维数组 A[n][n] 来保存图的信息A[i][j] 表示顶点 i 到顶点 j 的边。若是无权图可以用 0 和 1 表示是否存在边若是带权图则可以存权重不存在的边用一个很大的数表示。优点是写法极其简单判断两个顶点之间是否有边时间复杂度是 O(1)遍历某个顶点的邻接点也只需扫一行代码好写、不易出错。缺点也很明显空间复杂度是 O(n²)哪怕只有几条边矩阵依旧占了 n×n 个位置。对顶点数量大、边稀疏的图来说这是极大的浪费。我刚开始学的时候觉得邻接矩阵写起来太省事了结果遇到 n10000 的无权图直接用邻接矩阵就爆了内存。那个“n 稍微一上万矩阵就完蛋”的教训印象太深刻了。具体判断什么时候用邻接矩阵我的经验是顶点数不超过 1000且图相对稠密边数接近 n²或者需要频繁判断两点之间连通性时矩阵是可接受的选择否则尽量别碰。2.2 邻接表省空间适合稀疏图邻接表对每个顶点维护一个链表或动态数组存储所有与它相邻的顶点。对于无向图一条边会在两个顶点的链表中各出现一次对于有向图通常只在出边对应的顶点存储当然也可以额外维护逆邻接表方便找前驱。它最大的优势是空间复杂度为 O(ne)只存实际存在的边在稀疏图上优势巨大。遍历某个顶点的所有邻接点时时间复杂度是该顶点的度效率很高。代价是判断两点之间是否有直连边需要遍历链表不如矩阵直接。实际工程里邻接表是绝对的主流。操作系统里、网络分析软件里、图数据库里几乎都是邻接表或其变体因为它贴近现实场景——大多数真实图都是稀疏的社交网络虽然用户多但每个用户的好友数量远小于用户总数。数据结构实验报告里也经常让写一个图的邻接表实现这一步绕不过去。2.3 十字链表与邻接多重表进阶场景要提前知道有向图的存储如果既要快速找入边又要快速找出边可以考虑十字链表Orthogonal List。它用两个指针域分别指向下一条出边和入边相当于把邻接表和逆邻接表合在了一起。无向图的边如果希望避免重复存储一份边数据可以用邻接多重表Adjacency Multilist让一条边只对应一个边节点同时被两个顶点的链表引用。这两种结构在严蔚敏那本《数据结构C语言版》里介绍得很细但考试和平时做题用得不算多。我的建议是初学阶段先把邻接矩阵和邻接表吃透十字链表和邻接多重表做到能看懂、能说清结构即可不需要手写得很熟练。2.4 存储结构对比快速决策表存储方式空间复杂度判断两点相邻遍历某点邻接点适用场景邻接矩阵O(n²)O(1)O(n)稠密图、顶点数小邻接表O(ne)O(degree)O(degree)稀疏图、工程首选十字链表O(ne)较复杂入边/出边都高效有向图的深度分析邻接多重表O(ne)较复杂无向图的边操作频繁无向图的高级应用3. 图的遍历从起点出发把整个图都走一遍3.1 深度优先搜索DFS的递归本质与实现DFS 的思想一句话总结从某个顶点出发沿着一条路走到黑走不动了再退回来换一条路。它天然适合用递归来表达因为递归本身就是“递进”和“回溯”。假设我们用邻接表存储图用 C 语言写一个简单的 DFS#define MAXVEX 100 int visited[MAXVEX]; // 全局标记数组 void DFS(Graph *G, int v) { visited[v] 1; printf(%d , v); EdgeNode *p G-adjlist[v].firstedge; while (p ! NULL) { if (!visited[p-adjvex]) { DFS(G, p-adjvex); } p p-next; } } void DFSTraverse(Graph *G) { for (int i 0; i G-numVertexes; i) { visited[i] 0; } for (int i 0; i G-numVertexes; i) { if (!visited[i]) { DFS(G, i); // 处理非连通图 } } }这段代码里有一个特别容易出错的地方标记 visited 的时机。很多初学者会把标记写在递归调用之后导致同一个顶点被重复访问直接死循环。正确做法是在进入递归的那一刻就标记而不是在即将回溯时才标记。另外外层 for 循环是为了处理非连通图有些题目给出的是连通图你可能可以省略但保险起见一定要写上。3.2 广度优先搜索BFS的队列玩法BFS 的思想类似“水的波纹扩散”从起点开始先把所有邻居访问掉再按顺序访问邻居的邻居。它的实现离不开队列先让起点入队然后不断出队把出队顶点的所有未访问邻接点入队直到队列为空。C 语言里可以自己模拟一个队列或者直接用数组加头尾指针。关键代码核心轮廓如下void BFS(Graph *G, int v) { int queue[MAXVEX]; int front 0, rear 0; visited[v] 1; printf(%d , v); queue[rear] v; while (front rear) { int u queue[front]; EdgeNode *p G-adjlist[u].firstedge; while (p ! NULL) { if (!visited[p-adjvex]) { visited[p-adjvex] 1; printf(%d , p-adjvex); queue[rear] p-adjvex; } p p-next; } } }这里的细节是打印节点之后要马上标记 visited否则同一个邻接点可能被多个节点同时发现并重复入队队列里就会堆积大量重复元素最坏情况下会退化成指数级别。在 BFS 里visited 数组的更新时机简直是灵魂做 LeetCode 或《算法笔记》里的图论 BFS 题时这个坑我已经踩过好几次。3.3 两种遍历在算法题中的变形应用DFS 和 BFS 不只是用来“遍历输出顺序”的它们是很多图论算法的基础。连通分量个数对图执行一次完整的 DFS/BFS 遍历每一次外层循环进入新的 DFS/BFS就代表发现一个新的连通分量。这个思路可以用来判断图是否连通、求连通分量数量、判断是否为一棵树连通且边数为顶点数减一。环的检测DFS 中如果遇到一条边指向“正在递归栈中”的顶点说明存在环。这个“正在递归栈中”可以用另一个数组记录区分“已访问过”和“正在访问中”。二分图判断用 BFS 染色如果相邻顶点颜色相同则不是二分图。拓扑排序的 DFS 实现用 DFS 完成图的遍历后续遍历顺序反过来就是拓扑序经典做法。遍历是图论算法的基础建议你不仅会写递归版 DFS也试着把 DFS 改成显式栈的迭代版把 BFS 改成双向 BFS后面的最短路径和状态压缩搜索题里非常有用。4. 图的经典算法从最小生成树到最短路径4.1 最小生成树Prim与Kruskal的取舍最小生成树MST解决的问题是在一个带权无向连通图里找一棵包含所有顶点的树使得树中所有边的权重之和最小。两个经典算法必须掌握。Prim 算法从某个顶点开始每次从“已选集合”和“未选集合”之间的边里挑一条权重最小的边加入直到所有顶点都被收录。它适合稠密图时间复杂度 O(n²)如果用二叉堆优化可以降到 O((ne)logn)。实现时需要维护一个 lowcost 数组记录每个未选顶点到已选集合的最短距离。Kruskal 算法则是把所有边按权重从小到大排序依次尝试加入每条边用并查集判断会不会形成环不会形成环就保留。它适合稀疏图时间复杂度主要由排序决定 O(e·log e)。并查集是这里的关键前置知识不会并查集就没法写 Kruskal所以我建议你先把并查集的查找、合并、路径压缩都练熟。实际用哪个算法如果边数很少比如一个地图的村庄修路问题边明显远小于 n²用 Kruskal 很爽如果图的顶点数不多但边很密集就直接上 Prim。考试时一般会给邻接矩阵那就选 Prim给边集让你求 MST那就选 Kruskal这不只是技巧也是顺应不同数据结构的自然选择。4.2 最短路径Dijkstra、Bellman-Ford与Floyd最短路径可能是图论里最常用的算法了。Dijkstra 是单源最短路径的鼻祖但是它的前提是“权值非负”。它维护一个 dist 数组每次从未访问过的顶点里挑出当前距离最小的顶点然后松弛它的所有邻接边。用邻接矩阵实现时时间复杂度 O(n²)用优先队列优化后能达到 O((ne)log n)。Dijkstra 的经典实现里有一个必须注意的点选最小距离时不能用简单的遍历取 min 吗可以用但每次都要 O(n)整体 O(n²)。考试和手写代码没问题但如果是工程场景节点几十万就必须用“优先队列 邻接表”的组合选堆顶的时间降到 O(log n)。Bellman-Ford 算法允许负权边甚至能检测负环。它需要对所有边做 n-1 轮松弛时间复杂度 O(n·e)。SPFA 是它的队列优化版在稀疏图上表现优秀但最坏情况复杂度不稳定。考研重点是理解 Bellman-Ford 的原理为什么要做 n-1 轮因为一条最短路径最多包含 n-1 条边少一条边都不可能更短每轮至少确定一批顶点的最终距离。Floyd-Warshall 是多源最短路径的代表用动态规划的思路递推任意两点间的最短距离核心是一个三重循环for (int k 0; k n; k) for (int i 0; i n; i) for (int j 0; j n; j) if (dist[i][j] dist[i][k] dist[k][j]) dist[i][j] dist[i][k] dist[k][j];这段代码简单到令人发指但里面有个细节中间节点 k 必须是外层循环。如果 k 放在最内层那动态规划的顺序就错了算出来的结果不对。这个顺序我考研时背了很多遍但直到自己写实验才真正理解为什么 k 在外面——因为每一轮递推都要利用上一轮已经算好的“经过前 k-1 个中间点”的答案。4.3 拓扑排序与关键路径AOV/AOE网的工程意义拓扑排序针对有向无环图DAG解决的问题是把一堆有依赖关系的任务排出一个可行的执行顺序。比如大学课程有先修课的要求需要你给出一个合理的选课顺序拓扑排序就是干这个的。常见实现是 Kahn 算法先统计每个顶点的入度把所有入度为 0 的顶点入队然后不断出队把该顶点的所有邻接点的入度减 1发现某个顶点入度变成 0 就入队。最后如果入队的顶点数量小于图的顶点数量说明图中存在环无法完成拓扑排序。代码片段void TopologicalSort(Graph *G) { int indegree[MAXVEX]; // 计算每个顶点的入度省略 int queue[MAXVEX], front 0, rear 0; for (int i 0; i G-numVertexes; i) { if (indegree[i] 0) queue[rear] i; } while (front rear) { int v queue[front]; printf(%d , v); EdgeNode *p G-adjlist[v].firstedge; while (p ! NULL) { int k p-adjvex; if (--indegree[k] 0) { queue[rear] k; } p p-next; } } }关键路径则是建立在 AOE 网用边表示活动的有向无环图上用来求整个工程的最短完成时间以及哪些活动是关键活动、不能延误。求解过程基于拓扑序计算最早发生时间 ve再逆拓扑序计算最晚发生时间 vl最后 et lt 的活动就是关键活动。这个考点在 408 里属于综合应用题容易和拓扑排序一起出大题建议自己手动画一个 AOE 网推一遍千万别只看背诵结论。5. 408考研与面试里图怎么考5.1 王道408的图知识点梳理王道数据结构里把图放在第七章内容密度很高。常考的知识点大概有这么几块图的基本概念和术语比如有向图、无向图、度、路径、连通分量、强连通分量。图的存储邻接矩阵、邻接表、十字链表、邻接多重表。图的遍历DFS、BFS 的时间复杂度分析。图的应用最小生成树、最短路径、拓扑排序、关键路径。算法代码的书写尤其 Prim、Kruskal、Dijkstra、Floyd、拓扑排序的代码。408 的选择题喜欢出概念判断题比如“n 个顶点的无向图最多有多少条边”“一个图有 n 个顶点 n-1 条边一定是连通树吗”。综合题喜欢给一个具体的图让你写出 DFS/BFS 序列或者算关键路径。代码题则越来越重视像手写 Dijkstra 的代码在院校自命题和复试机试里很常见。我复习时的心得是先按存储结构把图的代码框架搭好邻接矩阵和邻接表的建图一定要达到“眼睛闭上都能写出来”的程度否则后面所有算法都无从下手。408 里很多图算法代码并不需要完整写出但核心逻辑必须清楚尤其是变量更新的时机。5.2 考试常见题型与代码题套路图相关的考试题翻来覆去就那几类手动模拟题给出邻接矩阵或邻接表让你写出从某个点出发的 DFS 序列、BFS 序列注意序列可能不是唯一的因为邻接点的访问顺序不同会得到不同结果。证明与计算题证明 Prim 算法正确性、计算最小生成树权重、计算关键路径长度等。代码题实现连通分量判断、判断有向图是否存在环、使用 Dijkstra 求最短路径、用 Kruskal 构造 MST 等。对着这几个类型做针对性练习比盲目刷题高效得多。我建议你准备一个“图论题库”笔记本把每种题型的模板代码整理好考试前反复默写。代码题最怕的是临场一边想思路一边写平时没有形成肌肉记忆。5.3 图论在真实业务里的落地图计算、图神经网络说完了考试我想聊聊图的“后劲”。现在前端经常听到“图计算”“图数据库”“图神经网络”这些热词其实它们底层都和图数据结构逃不开关系。图计算是处理大规模图数据的技术比如 PageRank、社区发现、社交网络分析图神经网络则是用深度学习建模图结构把节点表示成向量用于推荐系统、分子结构分析、知识图谱补全等。如果你后面做算法工程师会发现很多业务天然就是图用户的关注关系是图订单和商品之间的交互是图知识图谱更是典型的图。所以数据结构里的“图”不是只存在于教科书上的抽象概念它是很多高级技术的基石。有能力的话不妨在学完基础后去看一些开源图数据库或图计算框架的文档比如 Neo4j、NetworkX用它们跑一遍最短路径和最小生成树会对“图”有更立体的理解。6. 常见问题与避坑实录6.1 邻接矩阵溢出的坑我大学时写过一个城市公交路线分析的小实验顶点数大约 2000我偷懒用了邻接矩阵 int a[2000][2000]直接申请了 2000×2000×4 字节约 16MB单个数组还勉强能接受但是如果顶点数到 5000矩阵大小就到了 100MB 以上可能出现编译错误或运行时崩溃。更糟糕的是有些算法要保存多个二维数组dist、path、graph 等内存很容易爆。遇到这种情况第一反应应该是换邻接表或者用稀疏矩阵的存储方式。真正工程里的图通常是稀疏的邻接矩阵是“杀鸡用牛刀还切不动”。6.2 递归爆栈与迭代式DFSDFS 写递归确实最清晰但图特别大的时候递归深度可能达到几万甚至几十万层导致系统栈溢出。无论在校招面试还是 ACM 比赛中我都遇到过这种问题。解决办法是改成显式栈模拟递归void DFSIterative(Graph *G, int start) { int stack[MAXVEX], top -1; stack[top] start; visited[start] 1; while (top ! -1) { int v stack[top--]; printf(%d , v); EdgeNode *p G-adjlist[v].firstedge; while (p ! NULL) { if (!visited[p-adjvex]) { visited[p-adjvex] 1; stack[top] p-adjvex; } p p-next; } } }注意迭代版 DFS 的访问顺序和递归版不一定完全一致可能影响一些依赖“递增顺序”的输出结果但它能扛住大规模数据安全性好得多。6.3 写代码时容易犯的错误图论代码最常见的错误集中在三处visited 数组初始化遗漏多组测试数据跑同一个图时忘记清零 visited直接导致后续遍历不到任何节点。每组数据开始前必须重新初始化。图的编号从 0 开始还是从 1 开始很多题目顶点编号从 1 开始你写循环时如果从 0 开始就会出现访问不到第一个顶点的问题或者数组越界。建图时要明确下标语义。边重复插入无向图用邻接表时一次 addEdge 需要同时把 a 添加到 b 的链表、把 b 添加到 a 的链表如果只添加一边遍历时就漏边。我见过太多人在这里漏写一行代码。6.4 调试图论代码的实用技巧调试图论的代码用打印大法是最快的。建议单独写一个 printGraph 函数把邻接表或邻接矩阵完整打印出来确认建图是否正确。这一步很多初学者会省但调试最短路径算法时你要是不知道图里存的到底是什么会陷入“明明算法没问题结果就是不对”的假象中。其次遇到最短路径结果不对可以先在小图上手算一遍再对照代码里的 dist 数组每一轮的变化能很快定位是松弛逻辑错了还是选点逻辑错了。别嫌这一步慢我调试 Floyd 的三层循环时就是靠逐轮手算才发现了 k 层顺序的问题。7. 写在最后图的进阶路线建议图这块既深又广初学时很容易被各种概念淹没。我个人的体会是别急着背所有东西先从最小规模的图开始亲手画一画邻接矩阵和邻接表跑通 DFS/BFS再一步步加上最短路径和最小生成树。当你发现一个“图”能解决真实的路径规划、任务调度、社交关系分析问题时那种成就感是链表和树给不了的。最后再分享一个小技巧学图的时候强烈建议准备一个“模板代码仓库”按邻接矩阵、邻接表、DFS、BFS、Dijkstra、Prim、Kruskal、Floyd、拓扑排序、关键路径的顺序整理好每个模板都自己手写一遍。写多了以后考试和面试时根本不需要现场思考手到擒来。这样不仅能应付数据结构这门课再往后的图论算法竞赛、图计算和图神经网络学习你也能带着一套扎实的底子继续深入。
