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(n+e)。而邻接矩阵无论如何都是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的距离为0，A到其他城市的距离未知，设为无穷大。
第一步，选择距离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((m+n)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是一个逐步扩展中间顶点集合的过程：每处理完一个k，dist矩阵中任意两点间的路径就允许经过前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(n+e)。这个过程还有一个重要用途：检测图中是否存在环。如果处理完队列之后，输出的顶点数少于图中的顶点总数，说明图中存在环，拓扑排序无法完成。这在实际项目里非常有用——比如检测任务调度系统中是否出现循环依赖，检测数据库表之间的外键关系是否存在环路。
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的图存储原理，看看工业界怎么处理超大图结构的存储与遍历。
我个人的经验是，图结构在初学者看来是各种算法的大杂烩，容易产生畏难情绪。但当你把存储结构吃透，把遍历烂熟于心，后面的最短路径、最小生成树、拓扑排序就是基于遍历思路的扩展，每一块都有清晰的主线。把这篇文章里的代码自己敲一遍，跑几个用例，你会发现在不知不觉中已经掌握了一整个算法体系。图这种结构，学会不只是应付考试和面试，更是在训练一种建模思维。现实中太多复杂关系都可以抽象成图，而一旦抽象成功，解决问题的路径往往就清晰了。
