1. 图的存储结构选型邻接矩阵与邻接表的深度抉择写数据结构图这篇续作之前先聊个有意思的现象。上篇我们讨论了图的基本概念、术语和抽象数据类型这次一上来就得面对一个绕不开的问题图到底怎么存在内存里很多初学者觉得这有啥好纠结的矩阵往那一摆多直观。但我做了这么多年算法相关的开发可以负责任地说存储结构选错了后面所有算法跑起来全是事。1.1 邻接矩阵简单粗暴但空间敏感邻接矩阵是最符合直觉的存储方式。假设图中有n个顶点我们就开一个n乘n的二维数组matrix[i][j]的值表示顶点i到顶点j是否有边连接。有同学可能会问为什么不直接用链表或者数组列表因为矩阵有一个光学特性——任意两个顶点之间是否存在边时间复杂度是O(1)直接在数组中按下标访问即可。我用一个生活化类比来解释。想象你住在一个有100户人家的小区每户门前挂一块小白板记录自己和另外99户的关系。这种情况下你想知道A家和B家是不是熟人直接走到A家的白板前看B那一栏就行效率很高。但问题是100户人家就得准备100块白板每块白板写99条记录总共要9900条记录。如果扩大到1000户就是99.9万条记录。这空间代价肉眼可见地失控了。正因为这个特性邻接矩阵天然适合密集图也就是边数接近顶点数平方的图。在代码实现上最需要注意的是对角线元素初始化问题。无向图的邻接矩阵是对称的matrix[i][j]和matrix[j][i]必须同步更新很多新手在这里丢对称性后面遍历时就会发现各种诡异的问题。有向图则不必处理对称性只需要让matrix[i][j]指向边的方向。另外带权图里的matrix[i][j]直接存权重值不存在的边用无穷大表示。这里面有个小坑无穷大不能设成INT_MAX因为后面做最短路径算法时要执行加法操作INT_MAX加任何正数直接溢出变成负数程序就崩了。我一般习惯用0x3f3f3f3f这个值足够大而且两个它相加也不会超过int上限。1.2 邻接表稀疏图的首选方案邻接表的思路完全不同。我们把每个顶点看作一个链表的头节点后面挂着的节点就是它所有邻接点。继续用小区类比——每户人家不再挂白板了而是拿一个本子记录自己的朋友本子上有多少熟人取决于实际关系没有关系的完全占用不到空间。对于n个顶点、e条边的稀疏图邻接表只需要n个表头加2e个边节点无向图空间复杂度是O(ne)。而邻接矩阵无论如何都是O(n²)。在现实场景中社交网络、地图导航、网页超链接这些动辄百万甚至上亿顶点的图几乎都是稀疏的邻接表基本上是唯一选择。这就是为什么Redis底层实现某些图结构、或者图数据库neo4j的底层存储在逻辑上都更倾向类似邻接表的思想。邻接表实现时有一个细节容易被忽略边节点在插入时可以头插也可以尾插。头插的代码短但遍历顺序会逆序尾插更符合阅读直觉但每次都要走到链表末尾。如果图构建完就很少改动了头插配合逆序遍历是完全够用的性能还更高。还有一种是十字链表和邻接多重表它们在邻接表基础上做了优化用于有向图快速找入边、无向图避免存储冗余边。但说实话日常业务开发中接触得少考研和面试时知道其存在、理解设计动机就够了不必投入太多精力手写实现。1.3 存储结构选择决策树再也不纠结很多初学者问我怎么决定用哪种结构。我给的判断标准很简单粗暴看边数。如果边数e接近n²的10%以上或者图很密集直接邻接矩阵如果e约为n的量级甚至更小用邻接表。还有一种情况如果算法需要频繁判断两个顶点是否相邻用邻接矩阵能省下大量遍历链表的时间。但如果你做的是需要频繁增加和删除边的动态图邻接表维护起来更灵活。我自己的实践经验是第一版先写邻接表因为大部分算法DFS、BFS、Dijkstra、拓扑排序在邻接表上跑得更自然代码也更简洁。只有在判断两点是否邻接成为瓶颈时才改造为邻接矩阵。这个思路应用到生产环境里基本可以覆盖90%以上的业务场景。2. 图的遍历算法从点出发看遍全图图的遍历和树的遍历有本质不同。树有天然的层次结构从根节点出发可以无重复地访问所有节点因为树没有环。图不一样图中的环会导致同一个节点被重复访问。所以遍历图时第一件事就是准备一个visited数组记录哪些顶点已经访问过了。这个问题我认为是图算法中最基础也最重要的一个判断后面所有高级算法——联通分量计算、拓扑排序、关键路径、最短路径——都建立在正确的遍历之上。2.1 深度优先搜索递归背后的系统栈真相深度优先搜索DFS的思路可以这样理解从起点出发沿着一条路走到黑发现有路就走走不通再退回上一个岔路口换一条路。这个“退回”的过程专业叫回溯。从一个节点的视角来看DFS的逻辑是标记当前节点已访问然后遍历它的所有邻接点如果发现某个邻接点还没访问过就递归进入该节点。递归的终止条件是当前节点没有未访问的邻接点。用C语言写出来就是经典的十几行代码。void DFS(Graph* G, int v, int visited[]) { visited[v] 1; printf(%d , v); for (int w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w)) { if (!visited[w]) { DFS(G, w, visited); } } }注意FirstNeighbor和NextNeighbor这两个函数依赖具体存储结构。邻接矩阵实现时就是遍历一行找非零元素邻接表实现时就是遍历链表。递归实现的DFS虽然代码简洁但如果图的规模很大比如几十万个顶点递归会不断压栈可能导致系统栈溢出。实践中我经常用显式栈替换递归效果等同但可控性更强。显式栈版本的核心思想是把待访问的节点压栈每次弹出后检查并压入未访问的邻接点。DFS在解决可达性问题、岛屿数量问题、连通分量划分时非常高效。力扣上那些图论题目百分之七八十都能用DFS直接解。2.2 广度优先搜索队列实现的分层探索广度优先搜索BFS的思路完全相反。它不是一条路走到底而是从起点出发像石子投水一样一圈一圈扩散。从哪个顶点出发先把它的所有邻接点都访问完然后再访问这些邻接点的邻接点。这个策略保证了一个重要性质在无权图中BFS访问到的顶点顺序就是它们到起点的最短距离顺序。BFS用队列实现这几乎是固定的套路。void BFS(Graph* G, int start, int visited[]) { int queue[MAXV]; int front 0, rear 0; visited[start] 1; queue[rear] start; while (front rear) { int v queue[front]; printf(%d , v); for (int w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w)) { if (!visited[w]) { visited[w] 1; queue[rear] w; } } } }BFS一个经典的坑是邻接点入队时要立刻标记visited而不是出队时才标记。如果等出队再标记同一个顶点可能被多个邻接点重复入队队列里就会出现重复元素导致死循环或错误结果。这一点我在带实习生时反复强调但总有人踩。队列用数组实现时还要注意环形队列的空间管理rear和front的移动都要取模。如果图规模不大直接用固定数组模拟就行但生产环境建议用动态扩容的队列。2.3 连通分量与遍历次数之间的关系有一个非常实用的小结论对一个图执行DFS或BFS时需要启动几次遍历这个图就有几个连通分量。如果从某个顶点出发一次就能访问所有顶点说明这个图是连通的否则需要从其他未访问顶点再次启动遍历每启动一次就多一个连通分量。我做语义网络分析时经常用这个性质。比如100万个节点代表网页页面之间的链接构成有向图求连通分量的数量就能快速了解整个网络被分成了多少个大块。这在内容推荐系统里很有用——不同连通分量往往代表不同语义社区。针对非连通图的遍历外层必须再包一层循环for (int i 0; i G-n; i) { if (!visited[i]) { BFS(G, i, visited); } }3. 最短路径从导航软件到网络路由的核心算法最短路径是图论里应用最广的算法之一。你用高德地图导航时从A点到B点怎么走最近你浏览网页时浏览器怎么决定数据包的转发路径甚至你在社交平台看二度人脉推荐——这些场景背后都有最短路径算法的影子。求最短路径有两条经典路线单源最短路径的Dijkstra算法以及所有顶点对之间最短路径的Floyd算法。这两者的适用场景和复杂度差距巨大选错会增加不必要的工程量。3.1 Dijkstra算法贪心策略的教科书级应用Dijkstra算法解决的是单源最短路径问题即给定一个起点求它到其他所有顶点的最短距离。算法的核心思想是贪心每次从未确定最短路径的顶点中选一个距离起点最近的顶点把它的距离固定下来然后用这个顶点更新其他顶点的距离。我用一个具体的算法过程来解释。假设图有五座城市起点是A。初始化时A到A的距离为0A到其他城市的距离未知设为无穷大。第一步选择距离A最近且未访问的顶点这个顶点自然是A本身。访问A后更新A的邻接城市B和C的距离。第二步从未访问的城市中找距离A最近的假设是B距离为3。这时B的最短距离就确定是3了。不信可以检验一下还能不能找到一条从A到B比3还短的路径如果经过其他城市路径肯定要先经过某个未访问城市但从A到那个城市的距离本身已经大于3了那么整体路径一定更长。这里的贪心之所以能成立关键前提是图中不存在负权边。只要有负权边贪心选取的“最短”距离可能在后续被一条负边更新得更短Dijkstra就失效了。第三步用B更新邻接点。假设B到C有边权为2那么A经过B到C的距离为3加2等于5如果之前的距离是10就更新为5。重复这个过程直到所有顶点都被访问。核心代码框架如下void Dijkstra(Graph* G, int start, int dist[], int path[]) { int visited[MAXV] {0}; for (int i 0; i G-n; i) { dist[i] INF; path[i] -1; } dist[start] 0; for (int i 0; i G-n - 1; i) { // 找到未访问顶点中dist最小的 int u -1, minDist INF; for (int j 0; j G-n; j) { if (!visited[j] dist[j] minDist) { minDist dist[j]; u j; } } if (u -1) break; visited[u] 1; // 用u更新邻接点 for (int v 0; v G-n; v) { if (!visited[v] G-matrix[u][v] ! INF dist[u] G-matrix[u][v] dist[v]) { dist[v] dist[u] G-matrix[u][v]; path[v] u; } } } }path数组记录每个顶点最短路径上的前驱节点最后通过回溯就能得到完整路径。邻接矩阵实现下每次找未访问最小dist都是O(n)一共进行n轮复杂度是O(n²)。如果改用邻接表加优先队列最小堆优化复杂度可以降到O((mn)log n)。当顶点数上万、边数也很大时堆优化版本几乎是必须的否则跑一次导航级别的最短路查询可能要等好几秒。3.2 Floyd算法动态规划处理多源最短路径如果需要求所有顶点之间的最短路径用Dijkstra跑n次总复杂度是O(n³)而Floyd算法也是O(n³)但代码实现极其简洁。它的核心思想是动态规划考虑经过某个中间点k是否能缩短顶点i到j的路径。转移方程是dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])三重循环最外层是中间点k里两层是端点i和j。代码只有几行for (int k 0; k n; k) { for (int i 0; i n; i) { for (int j 0; j n; j) { if (dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } }注意最外层循环必须遍历中间点k这一点不能混淆。如果把k放在内层结果就是错的。原理在于Floyd是一个逐步扩展中间顶点集合的过程每处理完一个kdist矩阵中任意两点间的路径就允许经过前k个顶点。这个“允许经过的顶点集合逐步扩大”的思路正是动态规划中状态转移的核心。Floyd算法也支持负权边只要没有负权环就行。从这一点来说它比Dijkstra适用范围更广。不过实际生产中用Floyd的时候不多除非图规模在几百个节点以内。我之前做过一个物流路径分析项目图里有300多个城市节点用Floyd矩阵预计算所有城市对的最短距离跑一次存到数据库之后的所有查询都是O(1)查表体验非常好。3.3 负权边的坑与Bellman-Ford如果图中有负权边且没有负权环Dijkstra不能用Floyd可以。但如果图很大Floyd的O(n³)又扛不住这时候需要Bellman-Ford算法。它的思路是对所有边进行n-1轮松弛操作。每一轮松弛至少能让最短路径的边数多一n-1轮后最长简单路径最多n-1条边所以一定是收敛的。虽然Bellman-Ford的时间复杂度是O(n·e)一般比堆优化的Dijkstra慢但它天然支持负权边还能检测负权环。实际应用中比如某些金融套利检测场景边权是汇率取对数后的负数就会出现负权环这时候Bellman-Ford是唯一合理的选择。4. 最小生成树代价最低的连通方案最小生成树解决的问题和最短路径完全不是一回事。最短路径是“从A到B怎么走最近”而最小生成树是“用最少的边把所有顶点连起来”。一个面向点对点一个面向全局连通。很多初学者把这两个问题搞混我见过的面试答错案例太多了这里先划清界限。4.1 Prim算法从单个顶点扩张的势力范围Prim算法的思路很直观。从任意一个顶点出发把它加入已选集合。然后重复执行在所有连接已选集合和未选集合的边中找一条权值最小的边把这条边和连着的未选顶点加入集合。直到所有顶点都在集合中。它的贪心选择为什么正确可以用反证法理解。假设最小生成树中不包含当前的最小连接边e那么树上一定存在一条跨过已选集合和未选集合的边f。把e替换掉f得到的树连通性不变但总权值更小矛盾。这个证明逻辑就是MST性质。Prim算法实现时有一个关键技巧维护一个lowCost数组记录每个未选顶点到已选集合的最小边权。每次选出一个最小lowCost对应的顶点加入集合同时更新其他顶点的lowCost。这样每次找最小边只需要O(n)总共O(n²)。邻接矩阵实现下Prim算法特别舒服。void Prim(Graph* G, int start) { int lowCost[MAXV]; int parent[MAXV]; for (int i 0; i G-n; i) { lowCost[i] G-matrix[start][i]; parent[i] start; } for (int i 0; i G-n - 1; i) { int u -1, minCost INF; for (int j 0; j G-n; j) { if (lowCost[j] ! 0 lowCost[j] minCost) { minCost lowCost[j]; u j; } } printf(edge: %d-%d, weight: %d\n, parent[u], u, lowCost[u]); lowCost[u] 0; // 标记已选 for (int v 0; v G-n; v) { if (G-matrix[u][v] lowCost[v]) { lowCost[v] G-matrix[u][v]; parent[v] u; } } } }lowCost为0表示顶点已经在生成树集合中。这里有一个容易出错的地方更新的时候要判断lowCost[v] ! 0否则会把已经在树里的顶点又选一遍。4.2 Kruskal算法边排序加并查集的经典组合Kruskal算法的思路完全反过来。它直接把所有边按权值从小到大排序然后从小到大尝试加入边每次加入前检查这条边的两个端点是否已经连通。如果不连通就加入这条边如果已经连通跳过。这个过程用到了一种非常重要的数据结构——并查集。并查集维护每个顶点所属的集合能快速判断两个顶点是否在同一个集合中以及合并两个集合。最经典的实现是路径压缩加按秩合并查询和合并的均摊复杂度接近O(1)。int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unionSets(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootY] rootX; } }Kruskal的时间复杂度主要花在边排序上O(e log e)。如果图是稀疏图边的数量远小于顶点数的平方Kruskal会有明显优势。如果图是密集图Prim的O(n²)往往更高效。所以在生产环境中稀疏图用Kruskal密集图用Prim这是一个通用的选择准则。4.3 什么时候生成树算法派得上用场最小生成树的应用比想象中广泛。电力网规划多个城市之间架设电线每条线路有造价目标是用最小总造价让所有城市通电。通信基站组网确保所有基站连通同时总光纤长度最短。图像分割领域里基于最小生成树的聚类算法也很有名——把像素作为顶点灰度差作为边权对最小生成树做切割就能实现简单的图像区域分割。另外值得一提的是最小生成树和最短路径树的区别在构建网络拓扑时一定要想清楚。有些场景要的是全局最优连通用MST有些场景要的是每个节点到核心节点的延迟最低应该用最短路径树。这是两个不同的优化目标不能混用。5. 拓扑排序与关键路径有向无环图里的工程调度哲学拓扑排序解决的是一类前置依赖问题。大学课程安排里修读“数据结构”之前必须先修“程序设计基础”修读“操作系统”之前必须修完“数据结构”和“计算机组成原理”。这种课程之间的先修关系天然构成一个有向无环图DAG。拓扑排序就是给出一种满足所有依赖约束的线性序列。5.1 拓扑排序算法不断摘下入度为零的节点拓扑排序的算法过程很简单统计每个顶点的入度把入度为0的顶点放入队列。然后不断从队列中取出顶点输出它同时将它所有邻接点的入度减1。如果某个邻接点入度变为0就加入队列。这里使用队列和栈没有本质区别只是输出顺序会变。如果希望先输出编号小的可以用优先队列。如果用邻接表存储图拓扑排序的时间复杂度是O(ne)。这个过程还有一个重要用途检测图中是否存在环。如果处理完队列之后输出的顶点数少于图中的顶点总数说明图中存在环拓扑排序无法完成。这在实际项目里非常有用——比如检测任务调度系统中是否出现循环依赖检测数据库表之间的外键关系是否存在环路。void TopologicalSort(Graph* G) { int indegree[MAXV] {0}; // 统计入度 for (int i 0; i G-n; i) { for (int w FirstNeighbor(G, i); w 0; w NextNeighbor(G, i, w)) { indegree[w]; } } int queue[MAXV], front 0, rear 0; for (int i 0; i G-n; i) { if (indegree[i] 0) { queue[rear] i; } } int count 0; while (front rear) { int v queue[front]; printf(%d , v); count; for (int w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w)) { if (--indegree[w] 0) { queue[rear] w; } } } if (count ! G-n) { printf(Graph has cycle!\n); } }5.2 关键路径项目管理中哪些环节拖不得关键路径是在AOE网边表示活动的有向无环图上求工程的最短完成时间。每个事件表示一个时间点每条边表示一个活动边的权值是活动耗时。从源点到汇点的最长路径就是关键路径关键路径上的活动称为关键活动。为什么是“最长”路径因为整个工程要等所有路径的活动都完成后才能结束而最慢的那条路径决定了总工期。如果关键活动延误总工期一定会延长如果非关键活动延误只要不超过其松弛时间总工期可以不受影响。求关键路径的步骤是先求每个事件的最早发生时间ve从源点往前推取最大值再求每个事件的最迟发生时间vl从汇点往前推取最小值然后计算每条边的松弛时间松弛时间为0的边就是关键活动。这一套计算逻辑在项目管理软件里非常实用。之前做一个研发排期系统时我用拓扑排序加关键路径算法自动识别项目中的关键任务链标注出哪些任务延期会影响整体上线时间帮助项目经理精准安排资源。原理不复杂但带来的效率提升立竿见影。6. 图在实际业务系统中的落地案例光讲算法不落地总觉得隔了一层。分享两个我实际做过的案例说明图结构怎么在业务系统里落地。6.1 社交关系中的二度人脉推荐社交App的“你可能认识的人”功能本质上是遍历当前用户好友的好友。先用邻接表存储用户关系然后BFS深度为2排除掉已经是好友的人再按共同好友数量排序取Top N。实现不复杂但数据规模上来后要做好剪枝和缓存。6.2 Redis中跳表与图思想Redis的有序集合底层用了跳表虽然严格说不是图结构但它内部的层次结构可以用有向无环图来理解每一层索引节点指向下一层同一元素的指针构成了一个多层DAG。理解图结构帮助我快速理解跳表查询O(log n)的原理也更容易排查一些RDB持久化时出现的层级错乱问题。如果你想深入学习我给你三个方向建议。第一把LeetCode上图的题目按标签刷一遍重点关注岛屿问题、拓扑排序、最短路、并查集四大类。第二尝试用C或Java实现一个图类封装邻接表和邻接矩阵自己写一遍DFS和BFS再实现一个Dijkstra堆优化版本。第三读一读开源项目源码比如LevelDB的跳表实现、Neo4j的图存储原理看看工业界怎么处理超大图结构的存储与遍历。我个人的经验是图结构在初学者看来是各种算法的大杂烩容易产生畏难情绪。但当你把存储结构吃透把遍历烂熟于心后面的最短路径、最小生成树、拓扑排序就是基于遍历思路的扩展每一块都有清晰的主线。把这篇文章里的代码自己敲一遍跑几个用例你会发现在不知不觉中已经掌握了一整个算法体系。图这种结构学会不只是应付考试和面试更是在训练一种建模思维。现实中太多复杂关系都可以抽象成图而一旦抽象成功解决问题的路径往往就清晰了。