打开任何一个地图导航App输入起点和终点系统几乎瞬间就能给你算出一条甚至好几条推荐路线。你有没有想过这种瞬间背后到底发生了什么答案就藏在数据结构里那张看不见摸不着的图里。微信好友关系、网页间的跳转链接、芯片上几亿个晶体管的连接、甚至机器人走进一间陌生房间后对环境建立的地图模型本质上都是图。数据结构这门课里线性表解决一对一的问题树解决一对多的问题而图解决的是最复杂也最普遍的多对多关系。如果你正在学数据结构、准备408考研或者工作中突然要处理依赖关系、路径规划一类的问题这篇文章就是写给你的。我会把图的核心概念、存储方式、遍历算法、高频考点和工程应用串成一条线顺便把我在学习和调代码过程里踩过的坑也一并交底。1. 图到底在描述什么从朋友圈到导航路线都用同一套语言1.1 图和线性表、树的最大区别多对多的关系网络先别急着背定义。数据结构里讲图讲的不是怎么画一张图而是一种数学结构。它的正式定义是两个集合顶点集合V和边集合E记作G(V, E)。V里面装的是元素E里面装的是元素之间的关系。比如你的微信好友列表里每个人就是一个顶点你和某个好友之间的好友关系就是一条边。对比一下三种结构你会发现图的特殊之处非常明显。线性表是元素排成一条线每个元素最多有一个前驱和一个后继这是一对一树是层级关系每个节点可以有多个孩子但只有一个父节点根节点除外这是一对多而图允许任意两个顶点之间都有可能有关系这就是多对多。举一个直观的例子你在公司里的同事关系就不是一棵树能描述的——你有多个同事每个同事又有自己的多个同事关系网是交织的这种交织关系只能靠图来承载。1.2 关键术语一网打尽有向、无向、带权、连通图的术语乍一看很多但它们之间是有逻辑脉络的我按边这个核心来串无向边 vs 有向边微信好友关系是双向的你加了对方对方也就有了你这叫无向图。微博关注关系是单向的你关注了大V大V不一定关注你这叫有向图有向图的边又叫弧带箭头。带权图给每条边加一个数字叫权重。地图导航里两个路口之间的道路长度就是边的权值航班网络中两个城市之间的机票价格也是权值。没有权值的图叫无权图它只关心连不连不关心有多重。度无向图中一个顶点连接的边数叫度。有向图中还要区分入度和出度入度是指向我的边数出度是我指出去的边数。微博里你的粉丝数就是入度你关注的人数就是出度理解起来很直观。路径、回路、连通从一个顶点沿着边走到的另一个顶点经过的顶点序列就是路径。如果起点终点相同叫回路。无向图中任意两个顶点之间都有路径那这个图就是连通图有向图则要求两个方向都能到达叫强连通图。1.3 一张表盘点图的经典应用场景术语背得再多不如直接看它长在哪些真实场景里。我这里整理了一个清单你会发现图的抽象能力惊人地强应用场景顶点代表什么边代表什么有向/无向是否带权社交好友关系用户好友关系无向无权微博关注关系用户关注关系有向无权地图导航路口/地点道路有向单向路带权课程先修关系课程先修依赖有向无权电商推荐用户和商品购买/浏览行为有向带权知识图谱实体实体间关系有向带权看到这你应该明白了图的魅力不在于它本身多复杂而在于它能把一堆看似完全不同的现实问题统一成顶点边的数学表达。理解这一层后面的存储和算法才有意义。2. 邻接矩阵与邻接表的选型博弈空间和时间总要牺牲一个图的概念清楚了接下来的核心问题就是在计算机里怎么把这张关系网存下来主流方案就两个——邻接矩阵和邻接表。这个选择直接影响你后续所有算法的时间复杂度和代码复杂度。2.1 邻接矩阵用一张二维表粗暴地装下所有关系邻接矩阵的思路非常直接开辟一个n行n列的二维数组A[i][j]就表示顶点i和顶点j之间有没有边。无权图用0和1表示没有和有带权图用0或无穷大表示没有用具体权值表示有。它的优点极其突出判断任意两个顶点是否相邻时间复杂度是O(1)数组按下标直接取。代码写起来也最简单一个二维数组就能搞定。但缺点同样致命空间复杂度是O(n^2)。如果一个图有10000个顶点那就要开一亿个int的位置而实际可能只有几万条边——大量空间被浪费了。所以邻接矩阵只适合稠密图也就是边数接近顶点数平方的图。对于无向图来说邻接矩阵是一个对称矩阵A[i][j]等于A[j][i]。理论上可以只存一半三角区域来省空间但实际考试和工程里一般没人这么干因为会把代码复杂度拉高而且现代计算机内存也足够大大部分场景没必要省这一点。2.2 邻接表为稀疏图量身定做的邻居名单邻接表的思路更像现实中的人际关系维护方式我不需要知道全城所有人是不是我的朋友我只需要维护我的好友列表。具体做法是开一个长度为n的数组数组每个位置对应一个顶点后面挂一条链表链表中依次存放这个顶点的所有邻居。比如顶点2连着顶点1、3、5那数组第2个位置后面就挂一个链表依次存储1、3、5。这种结构在稀疏图边数远小于n^2里表现极佳空间复杂度是O(ne)e是边数。而且如果你想遍历某个顶点的所有邻居直接顺着链表走就行这在很多算法里是非常高频的操作。但邻接表也有短板要判断顶点i和顶点j是否相邻你得遍历i的整条链表去找j时间复杂度是O(度)比邻接矩阵的O(1)慢。此外链表节点还要额外存指针每个节点有一个next字段的额外开销。2.3 两种存储方式实测对比该用哪个心里要有数我做了个对比表方便你一眼看懂两种结构在不同维度上的表现对比维度邻接矩阵邻接表空间复杂度O(n^2)O(ne)判断两点是否邻接O(1)O(度)遍历某顶点的所有邻居O(n)O(度)更高效适合场景稠密图稀疏图实现难度低中等无向图存储冗余存储两遍浪费一半空间每条边存两次节点仍需处理我的建议是考试做题、算法竞赛入门阶段优先用邻接矩阵因为它不容易写错调试方便工程实践、处理大规模真实数据首选邻接表。很多同学在一开始就纠结哪个更好其实这俩不是谁取代谁的关系而是按图的稀疏程度和你的核心操作来选。2.4 进阶存储结构十字链表与邻接多重表除了两大主流方案数据结构课程里还经常提两种进阶结构。十字链表专门为有向图设计每个节点同时记录从i出发指向j和被k指向的信息好处是能同时方便地获取入度和出度。邻接多重表则为无向图设计解决了邻接表里同一条边被存两次导致删边时需要处理两处指针的问题。这两种结构在考试里主要是概念题和画图题的考点真正需要你上手的场景很少但理解它们的出发点很重要一切存储结构的设计都是在特定操作找入边、删边、反向遍历和空间开销之间做取舍。这个思想贯穿整个数据结构课程。3. BFS与DFS的实现细节遍历顺序不同写法和坑也不一样图存好了接下来要面对的问题是怎么把图走一遍两种最基础的遍历方式——深度优先搜索DFS和广度优先搜索BFS是所有图论算法的地基。排序算法是数据结构的热身图的DFS/BFS才真正开始考验递归和队列的功底。3.1 DFS一条路走到黑撞了南墙再回头DFS的直觉特别好理解就像在迷宫里走随便选一个岔路一直往前走走到没有未访问的邻居时就沿原路退回来去试其他岔路。实现上最自然的写法是递归用一个visited数组记录哪些顶点已经访问过。// 邻接矩阵版DFS #define MAXV 100 int graph[MAXV][MAXV]; int visited[MAXV]; void dfs(int v, int n) { visited[v] 1; printf(访问顶点 %d\n, v); for (int i 0; i n; i) { if (graph[v][i] !visited[i]) { dfs(i, n); } } }这段代码只干三件事标记当前顶点、访问当前顶点、递归访问所有未访问的邻居。递归结束条件隐含在for循环里——已经没有未访问的邻居时函数自然返回。要注意visited数组必须在进入递归前就标记否则会出现重复访问甚至死循环。如果你用邻接表实现for循环就改成遍历链表的所有节点其他逻辑完全一样。DFS的时间复杂度邻接矩阵是O(n^2)邻接表是O(ne)差别主要在找邻居这一步的开销上。3.2 BFS像水波一样一层一层向外扩散BFS的直觉则是另一番景象你往平静的水面扔一块石头波纹会一圈一圈向外扩散。BFS从起点出发先访问离起点最近的顶点再访问它们的邻居再访问邻居的邻居像剥洋葱一样一层层推进。实现上不靠递归靠一个队列。// 邻接矩阵版BFS void bfs(int start, int n) { int queue[MAXV]; int front 0, rear 0; visited[start] 1; queue[rear] start; while (front rear) { int v queue[front]; printf(访问顶点 %d\n, v); for (int i 0; i n; i) { if (graph[v][i] !visited[i]) { visited[i] 1; queue[rear] i; } } } }BFS里最容易踩的坑是标记visited的时机。你必须在顶点入队的那一刻就标记它已访问而不是在出队的时候才标记。如果等到出队再标记同一个顶点可能会被多个邻居同时发现并重复入队队列里会出现大量重复元素严重时会导致算法行为错误、输出混乱。3.3 两种遍历怎么选看你想解决什么问题DFS和BFS能解决同一类问题比如判断连通性但在不同场景下各有明显的优劣需求推荐方案原因找一条可行路径DFS递归深入实现简单找最短路径无权图BFS第一次到达目标点时的路径一定最短判断图是否是二分图BFS/DFS均可染色法拓扑排序DFS后续顶点访问顺序天然可逆找连通分量个数BFS/DFS均可遍历整图计数即可处理大规模图预估空间DFS递归栈通常比队列浅在无权图中BFS找最短路径是一个特别经典的性质因为BFS是一层一层扩散的当它第一次到达目标顶点时必然经过了最少的边数。所以迷宫类问题、社交网络中你和某个人的距离是几度这类问题直接用BFS。DFS则是后来很多高级算法如Tarjan求强连通分量的底层模板所以两个都得练熟。3.4 遍历的隐藏技能连通性检测和环的发现遍历不只是把图走一遍它还能顺手解决很多问题。比如你在main函数里循环调用dfs或bfs每调用一次就找到了一个连通分量调用次数就是图的连通分量个数。这个方法在无向图中尤其常用。再比如判断一个图有没有环在无向图DFS中如果访问到一个已经访问过且不是当前递归路径上直接父节点的顶点说明存在环在有向图DFS中如果访问到递归栈中仍在栈内的顶点则说明存在环。这个思路是很多课程表是否能排类题目的核心——课程依赖关系如果成环就意味着有循环先修课表永远排不出来。4. 最短路径与最小生成树图论算法里的两座必考高地遍历只是图的入门操作真正让图的威力显现的是两类经典优化问题最短路径和最小生成树。它们不仅是数据结构期末考试和王道408复习的重头戏也是工程中路径规划、网络设计的基础。4.1 Dijkstra贪心思想的教科书级应用但它扛不住负权边Dijkstra算法解决的是单源最短路径问题给定一个起点求它到图中所有其他顶点的最短路径。它的核心思想是贪心维护一个dist数组记录起点到各点的当前最短距离每次从未确定的顶点中选一个dist最小的顶点作为确定点然后用它去松弛它的邻居——如果通过这个确定点到邻居的距离比原来记录的更短就更新记录。// Dijkstra核心松弛逻辑伪代码懂思路比背代码更重要 dist[start] 0; // 循环n-1次每次选一个不在S集合中、dist最小的顶点u for (i 0; i n; i) { u 不在集合S中且dist最小的顶点; S S ∪ {u}; for (v : u的所有邻居) { if (dist[v] dist[u] w(u, v)) { dist[v] dist[u] w(u, v); } } }这个算法为什么要求边权非负因为一旦存在负权边已经确定的最短路径可能就不是真正最短的——你后面可能通过一条负边把距离刷新得更小但贪心过程已经把它锁死了。这是考试里最容易被问到的概念点之一。朴素Dijkstra的时间复杂度是O(n^2)用优先队列堆优化后能降到O((ne)logn)后者是实际工程中更常用的版本。408考试里这两种复杂度都要掌握面试里也经常让手撕堆优化版本。4.2 Floyd三层循环暴力美学适合小规模全源最短路径如果题目要求的是所有顶点对之间的最短路径Dijkstra跑n遍也不是不行但Floyd算法用更简洁的三层循环就解决了。它的核心是动态规划允许中转顶点的范围逐步扩大dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])。// Floyd核心三层循环 for (k 0; k n; k) // 中转顶点 for (i 0; i n; i) for (j 0; j n; j) if (dist[i][j] dist[i][k] dist[k][j]) dist[i][j] dist[i][k] dist[k][j];这段代码简单到让人怀疑它是否真的有效但它确实能在O(n^3)时间内算完所有点对的最短路径。而且Floyd能处理负权边只要不存在负权回路这是它相比Dijkstra的一个优势。代价就是复杂度高n超过几百就会比较吃力所以实际中通常用在顶点数很少的稠密图上。关于Floyd我特别想提醒一点三层循环的中转顶点k必须在最外层。如果你把k放在最内层算法得到的是完全错误的结果。原理上只有k逐步扩大的时候允许中转的范围才是逐渐增长的这样动态规划才成立这个顺序问题考试中经常以某一步dist矩阵是什么的形式出现。4.3 Prim和Kruskal两种贪心思路长出的最小生成树最小生成树问题说的是在一个带权无向连通图中找一棵包含所有顶点、且边的总权值最小的树。两个主流算法思路差别很大选型标准也因此完全不同。Prim算法是从一个顶点开始生长维护一个已选顶点集合每次都从未选顶点中挑一个与已选集合之间边权最小的顶点加入重复n-1次。它适合稠密图时间复杂度O(n^2)可以用堆优化。Kruskal算法则是挑边思路把所有边按权值从小到大排序然后逐个尝试加入只要不形成环就保留直到选出n-1条边。判断是否成环要用到并查集这是它代码实现里最需要留意的部分。它适合稀疏图复杂度主要是对边排序的O(eloge)。需要强调一个通用结论同一个图中既可能有不同的最小生成树当权值相同的时候但所有最小生成树的边权和一定相同。如果你做题时发现两个算法得到不同的总权值那不是算法错了是你在模拟过程中算错了。4.4 这些算法在考试中怎么被考察以408和期末考试的经验来看图相关的算法题大多不是让你现场写完整代码而是考察三件事手工模拟给定一个图让你写出Dijkstra每轮dist数组的变化或者用Kruskal写出选边的顺序。这种题特别考验对算法执行过程的理解建议自己动手在纸上至少走三遍完整流程。复杂度与适用条件Dijkstra能不能处理负权边Floyd能不能处理负环Prim和Kruskal各自适合什么图这类送分题如果丢分基本是概念没吃透。代码改错和填空给你一段不完整的算法代码让你填关键几行。这就要求平时写代码时尽量自己默写不要只看不练。5. 图在真实世界中的投影从导航到图神经网络学数据结构的人经常会问一个问题我以后写业务代码真的用得到图吗答案不仅是用得到而且是到处都是图。只不过在工程里图不再以课本上的小例子出现而是换了件马甲。5.1 地图导航分层图、A*算法和双向搜索地图App处理的是上亿顶点、几十亿边的大规模图根本不可能直接用邻接矩阵存。真实系统会做分层处理把全国地图分成若干层级跨城导航先走高速层市内导航再细化到普通道路层这就是热搜里那个分层图的概念。路径搜索也通常不是纯Dijkstra而是用A*算法配合启发式函数加速向目标方向扩展双向BFS从起点和终点同时搜索也能显著减少搜索空间这些技术本质都是围绕图做性能优化。你每一次点导航都是在消费一次图算法服务。5.2 社交网络与图计算引擎在社交平台后端好友关系被存进图数据库或图计算引擎。经典的推荐逻辑你可能认识的人就是图上的操作计算你和目标用户的共同好友数量超过阈值就推荐。更高级的社区发现算法能把用户划分成不同圈子精准投放内容。图计算领域还有一个著名算法PageRank当年Google就是靠它给网页排序它本质上是把互联网看成一张有向图然后计算每个网页在图上的重要性。近年来火热的图数据库Neo4j等也是图理论在工程上的直接落地。5.3 任务调度、依赖解析和拓扑排序前端开发里npm/yarn的依赖解析、后端服务编排、编译器把源码编译成可执行文件都要处理谁依赖谁的关系。这里有一个专门针对有向无环图的算法叫拓扑排序把顶点排成一个线性序列使得所有边的方向都从前指向后。如果图里有环拓扑排序就做不出来。还记得前面提过的课程表能不能排那道经典题吗它就是拓扑排序的代表应用。这个算法实现上还可以顺便统计每个顶点的入度变化逻辑十分优雅。5.4 图神经网络GNN让深度学习吃下图这种数据传统深度学习处理的是规整的网格数据比如图片、语音、文本。但社交网络、分子结构、交通路网这些数据天生不是规整的怎么办呢图神经网络GNN就是专门解决这个问题的它通过消息传递机制让每个节点聚合邻居的特征学习节点和图的表示。现在很热的自适应图卷积就是对图卷积算子做的改进版本让模型能自适应地学习节点之间的依赖权重。这个方向同时吃透了图论和深度学习是近年AI领域的热点。5.5 其他你可能没想到的图应用ER图数据库设计里实体和实体之间的关系本质上就是一张图只不过工程师用图形化工具把它画出来辅助建模。UML类图软件工程里描述类和类之间继承、组合、依赖关系也是图标准建模工具StarUML里那个类图画法就是图论的直观应用。SLAM建图机器人走进陌生环境靠传感器数据构建环境地图本质是在实时地构建和维护一张图——路标是顶点观测关系是边。芯片与电路布线PCB布线软件里所有元件的引脚和连接关系就是一张带权图布线问题被建模为在图上求最短路或最小斯坦纳树。看到这么多领域共用一套顶点边的抽象你应该能理解为什么数据结构课程把图放在最后压轴——它吸收了你学过的数组、链表、树、队列、栈的所有技巧又为真实世界里最复杂的关系问题提供了统一表达。6. 写图代码最常见的五个坑我调了很久才发现图相关的代码和链表、树的代码有个很大的区别错误的栈、树代码通常立刻报错或者输出明显不对但图代码如果逻辑有瑕疵往往在小样例上看起来完全正常一上大数据就崩或者结果错误。这里我整理了自己和周围同学踩得最深的五个坑希望你绕开。6.1 无向图建边时忘记添加反向边无向关系意味着如果你是我的邻居我也是你的邻居。在邻接矩阵里你需要同时执行graph[i][j] graph[j][i] 1在邻接表里i的链表要插入jj的链表也要插入i。这个操作漏掉一半图的遍历结果就会少一大片顶点而且你很难立刻发现因为在某些测试数据下输出看起来还是对的。我的检查习惯是写完存图代码后先打印一遍整个图的结构用5个顶点的小图肉眼确认每条边是不是双向的。6.2 visited数组标记时机不对这个坑我在前面讲BFS时提过但值得再强调一遍DFS应该在进入递归时就标记BFS应该在入队时就标记。如果BFS等到出队再标记同一个顶点会被重复入队多次。在带环的图里这会导致队列无限膨胀程序甚至直接内存溢出。判断自己有没有踩坑的方法很简单在访问顶点时打印队列长度如果发现队列里有大量重复顶点那就是标记时机出了问题。6.3 邻接矩阵初始化时把对角线设成了1有些同学初始化邻接矩阵时会把对角线graph[i][i]设为1表示每个顶点和自己相连。这在大部分图算法里都是错的——自环会干扰Dijkstra和DFS的路径判断还会让遍历输出出现顶点i访问了自己这种诡异现象。除非题目明确允许自环否则初始化时对角线应保持为0无权图或0带权图中表示到自身距离为0但邻接关系上仍为0。6.4 递归深度导致栈溢出4000个顶点的图直接崩溃邻接矩阵或邻接表下的DFS递归在顶点数较大且图深度较深时会消耗大量系统栈空间。我实测过一个单链形状的图顶点1连2、2连3、3连4……顶点数到5000左右C语言的默认栈就会溢出了。这是算法逻辑正确但工程上不可用的典型例子。解决方案有两个方向一是改用显式栈模拟DFS用自己定义的栈结构不占系统栈二是增大系统栈空间比如某些OJ提交时用-Wl,-stack参数。面试时如果面试官问递归DFS在大规模图上有什么问题前一个回答更稳妥。6.5 表示不可达的无穷大乱选带权图里两点之间没有边时邻接矩阵存什么很多同学随手填一个很大的数比如99999或者INT_MAX。问题在于Floyd或Dijkstra的松弛操作里如果dist[u] INF溢出变成负数整个dist数组就全乱了。INT_MAX是特别危险的选择两个INT_MAX相加直接溢出。业界常用的Scheme是用0x3f3f3f3f约10.7亿因为它足够大而且两个0x3f3f3f3f相加不会溢出int范围。这个看起来毫无技术含量的小细节能帮你省掉一整晚的调试时间。除了上面五个坑还有下标从0开始还是从1开始的问题。教材通常约定顶点编号从1开始但C语言的数组下标从0开始写代码时很容易混。我的建议是写代码前先统一约定存图时在顶点编号和数组下标之间做一个显式映射或者在读入时直接全部减1。千万不要在算法内部再临时做 1/-1 的变换那种代码非常容易乱。7. 学习图的正确打开方式给正在啃书本的你一些真心建议说点个人经验。我见过太多初学者学图第一个动作就是打开教材开始背图的定义是……邻接表是……然后看算法伪代码以为自己懂了一上机全懵。图这个章节光看是看不会的。我的建议是把学习顺序反过来先拿一张纸画一个包含七八个顶点的无向图自己手动走一遍DFS和BFS用笔在纸上标记访问顺序再画一个带权图手动跑一遍Dijkstra和Prim把每轮dist或者lowcost数组的变化写下来。这个过程做完你对算法的理解会比你看十遍教材都深。市面上所有经典教材——严蔚敏的、王道408的——都很重视这个过程里面大量习题就是在让你做这种手动模拟。手动模拟之后一定要做的一件事是把代码默写出来。关掉书打开编辑器从定义结构体开始写完存图函数再写DFS和BFS再写Dijkstra。第一次默写一定会卡壳没关系卡壳的地方就是你理解的盲点。把卡壳的地方记下来回头看书然后再默写一遍。我在准备408那段时间Dijkstra完整默写了不下十遍到最后闭着眼都能写出来这对应试的帮助非常大。最后一个心得是善用可视化工具。网上有各种图算法可视化网站比如VisuAlgo你把自己输入的数据丢进去看它一步一步地执行颜色高亮每个正在访问的顶点那种原来如此的感觉比任何文字解释都来得强烈。说到底图是一种极其依赖空间想象的结构你脑中建立的图画越清晰代码写得就越顺。从笨拙地画图开始到默写完整的算法模板这个过程一旦走通你会发现图并没有想象中那么难。
图数据结构全景解析：从存储结构到最短路径与工程应用
打开任何一个地图导航App输入起点和终点系统几乎瞬间就能给你算出一条甚至好几条推荐路线。你有没有想过这种瞬间背后到底发生了什么答案就藏在数据结构里那张看不见摸不着的图里。微信好友关系、网页间的跳转链接、芯片上几亿个晶体管的连接、甚至机器人走进一间陌生房间后对环境建立的地图模型本质上都是图。数据结构这门课里线性表解决一对一的问题树解决一对多的问题而图解决的是最复杂也最普遍的多对多关系。如果你正在学数据结构、准备408考研或者工作中突然要处理依赖关系、路径规划一类的问题这篇文章就是写给你的。我会把图的核心概念、存储方式、遍历算法、高频考点和工程应用串成一条线顺便把我在学习和调代码过程里踩过的坑也一并交底。1. 图到底在描述什么从朋友圈到导航路线都用同一套语言1.1 图和线性表、树的最大区别多对多的关系网络先别急着背定义。数据结构里讲图讲的不是怎么画一张图而是一种数学结构。它的正式定义是两个集合顶点集合V和边集合E记作G(V, E)。V里面装的是元素E里面装的是元素之间的关系。比如你的微信好友列表里每个人就是一个顶点你和某个好友之间的好友关系就是一条边。对比一下三种结构你会发现图的特殊之处非常明显。线性表是元素排成一条线每个元素最多有一个前驱和一个后继这是一对一树是层级关系每个节点可以有多个孩子但只有一个父节点根节点除外这是一对多而图允许任意两个顶点之间都有可能有关系这就是多对多。举一个直观的例子你在公司里的同事关系就不是一棵树能描述的——你有多个同事每个同事又有自己的多个同事关系网是交织的这种交织关系只能靠图来承载。1.2 关键术语一网打尽有向、无向、带权、连通图的术语乍一看很多但它们之间是有逻辑脉络的我按边这个核心来串无向边 vs 有向边微信好友关系是双向的你加了对方对方也就有了你这叫无向图。微博关注关系是单向的你关注了大V大V不一定关注你这叫有向图有向图的边又叫弧带箭头。带权图给每条边加一个数字叫权重。地图导航里两个路口之间的道路长度就是边的权值航班网络中两个城市之间的机票价格也是权值。没有权值的图叫无权图它只关心连不连不关心有多重。度无向图中一个顶点连接的边数叫度。有向图中还要区分入度和出度入度是指向我的边数出度是我指出去的边数。微博里你的粉丝数就是入度你关注的人数就是出度理解起来很直观。路径、回路、连通从一个顶点沿着边走到的另一个顶点经过的顶点序列就是路径。如果起点终点相同叫回路。无向图中任意两个顶点之间都有路径那这个图就是连通图有向图则要求两个方向都能到达叫强连通图。1.3 一张表盘点图的经典应用场景术语背得再多不如直接看它长在哪些真实场景里。我这里整理了一个清单你会发现图的抽象能力惊人地强应用场景顶点代表什么边代表什么有向/无向是否带权社交好友关系用户好友关系无向无权微博关注关系用户关注关系有向无权地图导航路口/地点道路有向单向路带权课程先修关系课程先修依赖有向无权电商推荐用户和商品购买/浏览行为有向带权知识图谱实体实体间关系有向带权看到这你应该明白了图的魅力不在于它本身多复杂而在于它能把一堆看似完全不同的现实问题统一成顶点边的数学表达。理解这一层后面的存储和算法才有意义。2. 邻接矩阵与邻接表的选型博弈空间和时间总要牺牲一个图的概念清楚了接下来的核心问题就是在计算机里怎么把这张关系网存下来主流方案就两个——邻接矩阵和邻接表。这个选择直接影响你后续所有算法的时间复杂度和代码复杂度。2.1 邻接矩阵用一张二维表粗暴地装下所有关系邻接矩阵的思路非常直接开辟一个n行n列的二维数组A[i][j]就表示顶点i和顶点j之间有没有边。无权图用0和1表示没有和有带权图用0或无穷大表示没有用具体权值表示有。它的优点极其突出判断任意两个顶点是否相邻时间复杂度是O(1)数组按下标直接取。代码写起来也最简单一个二维数组就能搞定。但缺点同样致命空间复杂度是O(n^2)。如果一个图有10000个顶点那就要开一亿个int的位置而实际可能只有几万条边——大量空间被浪费了。所以邻接矩阵只适合稠密图也就是边数接近顶点数平方的图。对于无向图来说邻接矩阵是一个对称矩阵A[i][j]等于A[j][i]。理论上可以只存一半三角区域来省空间但实际考试和工程里一般没人这么干因为会把代码复杂度拉高而且现代计算机内存也足够大大部分场景没必要省这一点。2.2 邻接表为稀疏图量身定做的邻居名单邻接表的思路更像现实中的人际关系维护方式我不需要知道全城所有人是不是我的朋友我只需要维护我的好友列表。具体做法是开一个长度为n的数组数组每个位置对应一个顶点后面挂一条链表链表中依次存放这个顶点的所有邻居。比如顶点2连着顶点1、3、5那数组第2个位置后面就挂一个链表依次存储1、3、5。这种结构在稀疏图边数远小于n^2里表现极佳空间复杂度是O(ne)e是边数。而且如果你想遍历某个顶点的所有邻居直接顺着链表走就行这在很多算法里是非常高频的操作。但邻接表也有短板要判断顶点i和顶点j是否相邻你得遍历i的整条链表去找j时间复杂度是O(度)比邻接矩阵的O(1)慢。此外链表节点还要额外存指针每个节点有一个next字段的额外开销。2.3 两种存储方式实测对比该用哪个心里要有数我做了个对比表方便你一眼看懂两种结构在不同维度上的表现对比维度邻接矩阵邻接表空间复杂度O(n^2)O(ne)判断两点是否邻接O(1)O(度)遍历某顶点的所有邻居O(n)O(度)更高效适合场景稠密图稀疏图实现难度低中等无向图存储冗余存储两遍浪费一半空间每条边存两次节点仍需处理我的建议是考试做题、算法竞赛入门阶段优先用邻接矩阵因为它不容易写错调试方便工程实践、处理大规模真实数据首选邻接表。很多同学在一开始就纠结哪个更好其实这俩不是谁取代谁的关系而是按图的稀疏程度和你的核心操作来选。2.4 进阶存储结构十字链表与邻接多重表除了两大主流方案数据结构课程里还经常提两种进阶结构。十字链表专门为有向图设计每个节点同时记录从i出发指向j和被k指向的信息好处是能同时方便地获取入度和出度。邻接多重表则为无向图设计解决了邻接表里同一条边被存两次导致删边时需要处理两处指针的问题。这两种结构在考试里主要是概念题和画图题的考点真正需要你上手的场景很少但理解它们的出发点很重要一切存储结构的设计都是在特定操作找入边、删边、反向遍历和空间开销之间做取舍。这个思想贯穿整个数据结构课程。3. BFS与DFS的实现细节遍历顺序不同写法和坑也不一样图存好了接下来要面对的问题是怎么把图走一遍两种最基础的遍历方式——深度优先搜索DFS和广度优先搜索BFS是所有图论算法的地基。排序算法是数据结构的热身图的DFS/BFS才真正开始考验递归和队列的功底。3.1 DFS一条路走到黑撞了南墙再回头DFS的直觉特别好理解就像在迷宫里走随便选一个岔路一直往前走走到没有未访问的邻居时就沿原路退回来去试其他岔路。实现上最自然的写法是递归用一个visited数组记录哪些顶点已经访问过。// 邻接矩阵版DFS #define MAXV 100 int graph[MAXV][MAXV]; int visited[MAXV]; void dfs(int v, int n) { visited[v] 1; printf(访问顶点 %d\n, v); for (int i 0; i n; i) { if (graph[v][i] !visited[i]) { dfs(i, n); } } }这段代码只干三件事标记当前顶点、访问当前顶点、递归访问所有未访问的邻居。递归结束条件隐含在for循环里——已经没有未访问的邻居时函数自然返回。要注意visited数组必须在进入递归前就标记否则会出现重复访问甚至死循环。如果你用邻接表实现for循环就改成遍历链表的所有节点其他逻辑完全一样。DFS的时间复杂度邻接矩阵是O(n^2)邻接表是O(ne)差别主要在找邻居这一步的开销上。3.2 BFS像水波一样一层一层向外扩散BFS的直觉则是另一番景象你往平静的水面扔一块石头波纹会一圈一圈向外扩散。BFS从起点出发先访问离起点最近的顶点再访问它们的邻居再访问邻居的邻居像剥洋葱一样一层层推进。实现上不靠递归靠一个队列。// 邻接矩阵版BFS void bfs(int start, int n) { int queue[MAXV]; int front 0, rear 0; visited[start] 1; queue[rear] start; while (front rear) { int v queue[front]; printf(访问顶点 %d\n, v); for (int i 0; i n; i) { if (graph[v][i] !visited[i]) { visited[i] 1; queue[rear] i; } } } }BFS里最容易踩的坑是标记visited的时机。你必须在顶点入队的那一刻就标记它已访问而不是在出队的时候才标记。如果等到出队再标记同一个顶点可能会被多个邻居同时发现并重复入队队列里会出现大量重复元素严重时会导致算法行为错误、输出混乱。3.3 两种遍历怎么选看你想解决什么问题DFS和BFS能解决同一类问题比如判断连通性但在不同场景下各有明显的优劣需求推荐方案原因找一条可行路径DFS递归深入实现简单找最短路径无权图BFS第一次到达目标点时的路径一定最短判断图是否是二分图BFS/DFS均可染色法拓扑排序DFS后续顶点访问顺序天然可逆找连通分量个数BFS/DFS均可遍历整图计数即可处理大规模图预估空间DFS递归栈通常比队列浅在无权图中BFS找最短路径是一个特别经典的性质因为BFS是一层一层扩散的当它第一次到达目标顶点时必然经过了最少的边数。所以迷宫类问题、社交网络中你和某个人的距离是几度这类问题直接用BFS。DFS则是后来很多高级算法如Tarjan求强连通分量的底层模板所以两个都得练熟。3.4 遍历的隐藏技能连通性检测和环的发现遍历不只是把图走一遍它还能顺手解决很多问题。比如你在main函数里循环调用dfs或bfs每调用一次就找到了一个连通分量调用次数就是图的连通分量个数。这个方法在无向图中尤其常用。再比如判断一个图有没有环在无向图DFS中如果访问到一个已经访问过且不是当前递归路径上直接父节点的顶点说明存在环在有向图DFS中如果访问到递归栈中仍在栈内的顶点则说明存在环。这个思路是很多课程表是否能排类题目的核心——课程依赖关系如果成环就意味着有循环先修课表永远排不出来。4. 最短路径与最小生成树图论算法里的两座必考高地遍历只是图的入门操作真正让图的威力显现的是两类经典优化问题最短路径和最小生成树。它们不仅是数据结构期末考试和王道408复习的重头戏也是工程中路径规划、网络设计的基础。4.1 Dijkstra贪心思想的教科书级应用但它扛不住负权边Dijkstra算法解决的是单源最短路径问题给定一个起点求它到图中所有其他顶点的最短路径。它的核心思想是贪心维护一个dist数组记录起点到各点的当前最短距离每次从未确定的顶点中选一个dist最小的顶点作为确定点然后用它去松弛它的邻居——如果通过这个确定点到邻居的距离比原来记录的更短就更新记录。// Dijkstra核心松弛逻辑伪代码懂思路比背代码更重要 dist[start] 0; // 循环n-1次每次选一个不在S集合中、dist最小的顶点u for (i 0; i n; i) { u 不在集合S中且dist最小的顶点; S S ∪ {u}; for (v : u的所有邻居) { if (dist[v] dist[u] w(u, v)) { dist[v] dist[u] w(u, v); } } }这个算法为什么要求边权非负因为一旦存在负权边已经确定的最短路径可能就不是真正最短的——你后面可能通过一条负边把距离刷新得更小但贪心过程已经把它锁死了。这是考试里最容易被问到的概念点之一。朴素Dijkstra的时间复杂度是O(n^2)用优先队列堆优化后能降到O((ne)logn)后者是实际工程中更常用的版本。408考试里这两种复杂度都要掌握面试里也经常让手撕堆优化版本。4.2 Floyd三层循环暴力美学适合小规模全源最短路径如果题目要求的是所有顶点对之间的最短路径Dijkstra跑n遍也不是不行但Floyd算法用更简洁的三层循环就解决了。它的核心是动态规划允许中转顶点的范围逐步扩大dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])。// Floyd核心三层循环 for (k 0; k n; k) // 中转顶点 for (i 0; i n; i) for (j 0; j n; j) if (dist[i][j] dist[i][k] dist[k][j]) dist[i][j] dist[i][k] dist[k][j];这段代码简单到让人怀疑它是否真的有效但它确实能在O(n^3)时间内算完所有点对的最短路径。而且Floyd能处理负权边只要不存在负权回路这是它相比Dijkstra的一个优势。代价就是复杂度高n超过几百就会比较吃力所以实际中通常用在顶点数很少的稠密图上。关于Floyd我特别想提醒一点三层循环的中转顶点k必须在最外层。如果你把k放在最内层算法得到的是完全错误的结果。原理上只有k逐步扩大的时候允许中转的范围才是逐渐增长的这样动态规划才成立这个顺序问题考试中经常以某一步dist矩阵是什么的形式出现。4.3 Prim和Kruskal两种贪心思路长出的最小生成树最小生成树问题说的是在一个带权无向连通图中找一棵包含所有顶点、且边的总权值最小的树。两个主流算法思路差别很大选型标准也因此完全不同。Prim算法是从一个顶点开始生长维护一个已选顶点集合每次都从未选顶点中挑一个与已选集合之间边权最小的顶点加入重复n-1次。它适合稠密图时间复杂度O(n^2)可以用堆优化。Kruskal算法则是挑边思路把所有边按权值从小到大排序然后逐个尝试加入只要不形成环就保留直到选出n-1条边。判断是否成环要用到并查集这是它代码实现里最需要留意的部分。它适合稀疏图复杂度主要是对边排序的O(eloge)。需要强调一个通用结论同一个图中既可能有不同的最小生成树当权值相同的时候但所有最小生成树的边权和一定相同。如果你做题时发现两个算法得到不同的总权值那不是算法错了是你在模拟过程中算错了。4.4 这些算法在考试中怎么被考察以408和期末考试的经验来看图相关的算法题大多不是让你现场写完整代码而是考察三件事手工模拟给定一个图让你写出Dijkstra每轮dist数组的变化或者用Kruskal写出选边的顺序。这种题特别考验对算法执行过程的理解建议自己动手在纸上至少走三遍完整流程。复杂度与适用条件Dijkstra能不能处理负权边Floyd能不能处理负环Prim和Kruskal各自适合什么图这类送分题如果丢分基本是概念没吃透。代码改错和填空给你一段不完整的算法代码让你填关键几行。这就要求平时写代码时尽量自己默写不要只看不练。5. 图在真实世界中的投影从导航到图神经网络学数据结构的人经常会问一个问题我以后写业务代码真的用得到图吗答案不仅是用得到而且是到处都是图。只不过在工程里图不再以课本上的小例子出现而是换了件马甲。5.1 地图导航分层图、A*算法和双向搜索地图App处理的是上亿顶点、几十亿边的大规模图根本不可能直接用邻接矩阵存。真实系统会做分层处理把全国地图分成若干层级跨城导航先走高速层市内导航再细化到普通道路层这就是热搜里那个分层图的概念。路径搜索也通常不是纯Dijkstra而是用A*算法配合启发式函数加速向目标方向扩展双向BFS从起点和终点同时搜索也能显著减少搜索空间这些技术本质都是围绕图做性能优化。你每一次点导航都是在消费一次图算法服务。5.2 社交网络与图计算引擎在社交平台后端好友关系被存进图数据库或图计算引擎。经典的推荐逻辑你可能认识的人就是图上的操作计算你和目标用户的共同好友数量超过阈值就推荐。更高级的社区发现算法能把用户划分成不同圈子精准投放内容。图计算领域还有一个著名算法PageRank当年Google就是靠它给网页排序它本质上是把互联网看成一张有向图然后计算每个网页在图上的重要性。近年来火热的图数据库Neo4j等也是图理论在工程上的直接落地。5.3 任务调度、依赖解析和拓扑排序前端开发里npm/yarn的依赖解析、后端服务编排、编译器把源码编译成可执行文件都要处理谁依赖谁的关系。这里有一个专门针对有向无环图的算法叫拓扑排序把顶点排成一个线性序列使得所有边的方向都从前指向后。如果图里有环拓扑排序就做不出来。还记得前面提过的课程表能不能排那道经典题吗它就是拓扑排序的代表应用。这个算法实现上还可以顺便统计每个顶点的入度变化逻辑十分优雅。5.4 图神经网络GNN让深度学习吃下图这种数据传统深度学习处理的是规整的网格数据比如图片、语音、文本。但社交网络、分子结构、交通路网这些数据天生不是规整的怎么办呢图神经网络GNN就是专门解决这个问题的它通过消息传递机制让每个节点聚合邻居的特征学习节点和图的表示。现在很热的自适应图卷积就是对图卷积算子做的改进版本让模型能自适应地学习节点之间的依赖权重。这个方向同时吃透了图论和深度学习是近年AI领域的热点。5.5 其他你可能没想到的图应用ER图数据库设计里实体和实体之间的关系本质上就是一张图只不过工程师用图形化工具把它画出来辅助建模。UML类图软件工程里描述类和类之间继承、组合、依赖关系也是图标准建模工具StarUML里那个类图画法就是图论的直观应用。SLAM建图机器人走进陌生环境靠传感器数据构建环境地图本质是在实时地构建和维护一张图——路标是顶点观测关系是边。芯片与电路布线PCB布线软件里所有元件的引脚和连接关系就是一张带权图布线问题被建模为在图上求最短路或最小斯坦纳树。看到这么多领域共用一套顶点边的抽象你应该能理解为什么数据结构课程把图放在最后压轴——它吸收了你学过的数组、链表、树、队列、栈的所有技巧又为真实世界里最复杂的关系问题提供了统一表达。6. 写图代码最常见的五个坑我调了很久才发现图相关的代码和链表、树的代码有个很大的区别错误的栈、树代码通常立刻报错或者输出明显不对但图代码如果逻辑有瑕疵往往在小样例上看起来完全正常一上大数据就崩或者结果错误。这里我整理了自己和周围同学踩得最深的五个坑希望你绕开。6.1 无向图建边时忘记添加反向边无向关系意味着如果你是我的邻居我也是你的邻居。在邻接矩阵里你需要同时执行graph[i][j] graph[j][i] 1在邻接表里i的链表要插入jj的链表也要插入i。这个操作漏掉一半图的遍历结果就会少一大片顶点而且你很难立刻发现因为在某些测试数据下输出看起来还是对的。我的检查习惯是写完存图代码后先打印一遍整个图的结构用5个顶点的小图肉眼确认每条边是不是双向的。6.2 visited数组标记时机不对这个坑我在前面讲BFS时提过但值得再强调一遍DFS应该在进入递归时就标记BFS应该在入队时就标记。如果BFS等到出队再标记同一个顶点会被重复入队多次。在带环的图里这会导致队列无限膨胀程序甚至直接内存溢出。判断自己有没有踩坑的方法很简单在访问顶点时打印队列长度如果发现队列里有大量重复顶点那就是标记时机出了问题。6.3 邻接矩阵初始化时把对角线设成了1有些同学初始化邻接矩阵时会把对角线graph[i][i]设为1表示每个顶点和自己相连。这在大部分图算法里都是错的——自环会干扰Dijkstra和DFS的路径判断还会让遍历输出出现顶点i访问了自己这种诡异现象。除非题目明确允许自环否则初始化时对角线应保持为0无权图或0带权图中表示到自身距离为0但邻接关系上仍为0。6.4 递归深度导致栈溢出4000个顶点的图直接崩溃邻接矩阵或邻接表下的DFS递归在顶点数较大且图深度较深时会消耗大量系统栈空间。我实测过一个单链形状的图顶点1连2、2连3、3连4……顶点数到5000左右C语言的默认栈就会溢出了。这是算法逻辑正确但工程上不可用的典型例子。解决方案有两个方向一是改用显式栈模拟DFS用自己定义的栈结构不占系统栈二是增大系统栈空间比如某些OJ提交时用-Wl,-stack参数。面试时如果面试官问递归DFS在大规模图上有什么问题前一个回答更稳妥。6.5 表示不可达的无穷大乱选带权图里两点之间没有边时邻接矩阵存什么很多同学随手填一个很大的数比如99999或者INT_MAX。问题在于Floyd或Dijkstra的松弛操作里如果dist[u] INF溢出变成负数整个dist数组就全乱了。INT_MAX是特别危险的选择两个INT_MAX相加直接溢出。业界常用的Scheme是用0x3f3f3f3f约10.7亿因为它足够大而且两个0x3f3f3f3f相加不会溢出int范围。这个看起来毫无技术含量的小细节能帮你省掉一整晚的调试时间。除了上面五个坑还有下标从0开始还是从1开始的问题。教材通常约定顶点编号从1开始但C语言的数组下标从0开始写代码时很容易混。我的建议是写代码前先统一约定存图时在顶点编号和数组下标之间做一个显式映射或者在读入时直接全部减1。千万不要在算法内部再临时做 1/-1 的变换那种代码非常容易乱。7. 学习图的正确打开方式给正在啃书本的你一些真心建议说点个人经验。我见过太多初学者学图第一个动作就是打开教材开始背图的定义是……邻接表是……然后看算法伪代码以为自己懂了一上机全懵。图这个章节光看是看不会的。我的建议是把学习顺序反过来先拿一张纸画一个包含七八个顶点的无向图自己手动走一遍DFS和BFS用笔在纸上标记访问顺序再画一个带权图手动跑一遍Dijkstra和Prim把每轮dist或者lowcost数组的变化写下来。这个过程做完你对算法的理解会比你看十遍教材都深。市面上所有经典教材——严蔚敏的、王道408的——都很重视这个过程里面大量习题就是在让你做这种手动模拟。手动模拟之后一定要做的一件事是把代码默写出来。关掉书打开编辑器从定义结构体开始写完存图函数再写DFS和BFS再写Dijkstra。第一次默写一定会卡壳没关系卡壳的地方就是你理解的盲点。把卡壳的地方记下来回头看书然后再默写一遍。我在准备408那段时间Dijkstra完整默写了不下十遍到最后闭着眼都能写出来这对应试的帮助非常大。最后一个心得是善用可视化工具。网上有各种图算法可视化网站比如VisuAlgo你把自己输入的数据丢进去看它一步一步地执行颜色高亮每个正在访问的顶点那种原来如此的感觉比任何文字解释都来得强烈。说到底图是一种极其依赖空间想象的结构你脑中建立的图画越清晰代码写得就越顺。从笨拙地画图开始到默写完整的算法模板这个过程一旦走通你会发现图并没有想象中那么难。