1. 从“图”说起为什么我们需要一种新的数据结构如果你写过链表、树或者堆可能会觉得数据结构的世界已经足够丰富了。链表处理线性关系树处理层次关系堆处理优先级。但当我们面对更复杂的关系时比如社交网络中的好友关系、城市之间的交通路线、网页之间的超链接这些结构就显得力不从心了。这些关系不再是简单的“上一个/下一个”或者“父节点/子节点”而是呈现出一种多对多、网状交织的形态。这就是“图”登场的时刻。图论作为数学的一个古老分支研究的就是这种由“顶点”和连接顶点的“边”所构成的抽象结构。在计算机科学中图不再仅仅是理论模型而是解决无数实际工程问题的核心工具。从你手机里的地图App规划最短路径到电商平台给你推荐“购买此商品的人也买了...”再到编译器分析代码的依赖关系背后都有图论算法的身影。这一章我们将深入图的世界不仅理解其概念更要掌握用C这把利器去实现和操作它的方法。无论你是正在备战算法竞赛还是希望夯实基础以应对未来的系统设计面试这一章的内容都将是你工具箱里至关重要的一部分。2. 图的基石顶点、边与两种核心存储方式理解图首先要理解它的两个基本元素顶点和边。顶点代表实体比如一个人、一个城市、一个任务。边代表关系比如“认识”、“有道路连接”、“依赖于”。边可以是有方向的比如A关注了BA-B也可以是无方向的比如A和B是微信好友A-B。边还可以有权重代表关系的强度或成本比如道路的长度、通信的带宽。在C中我们如何将这种抽象的结构具象化地存储起来呢主要有两种主流方法邻接矩阵和邻接表。选择哪一种取决于你面对的是什么类型的图。2.1 邻接矩阵直观的“城市间直达航班表”想象一个N个城市的交通网。我们可以用一个N行N列的二维数组matrix来表示它。matrix[i][j] 1表示从城市i到城市j有直达航班对于无向图matrix[j][i]也应为1matrix[i][j] 0则表示没有。如果边有权重这里就可以存储权重值用一个大数如INT_MAX表示不连通。#include vector using namespace std; // 使用邻接矩阵表示一个最多有100个顶点的有向图 const int MAX_V 100; int graph[MAX_V][MAX_V]; int n; // 实际顶点数 void initGraph() { for (int i 0; i MAX_V; i) { for (int j 0; j MAX_V; j) { // 初始化自己到自己的距离为0其他为无穷大表示不连通 graph[i][j] (i j) ? 0 : INT_MAX; } } } void addEdge(int from, int to, int weight) { graph[from][to] weight; // 添加一条有向边 // 如果是无向图需要加上graph[to][from] weight; }邻接矩阵的优缺点非常鲜明优点查询极快判断任意两个顶点u和v之间是否有边直接访问graph[u][v]时间复杂度是O(1)。实现简单对于稠密图边数接近顶点数的平方这种表示法非常紧凑和高效。缺点空间消耗大需要O(V²)的空间V是顶点数。对于顶点数上万甚至百万的社交网络这个矩阵将大得无法存储。遍历邻居慢要找出顶点v的所有邻居你需要遍历一整行或列即使它只有一两个邻居也需要O(V)的时间。注意邻接矩阵是典型的“以空间换时间”的策略。在顶点数较少例如几百个且需要频繁进行“两点间是否有边”查询的场景下它是好选择。但对于顶点多、边相对稀疏的图如大多数社交网络它的空间浪费是致命的。2.2 邻接表高效的“个人通讯录”这更符合我们的直觉。我们为每个顶点维护一个列表记录它所有直接相连的邻居。在C中通常用vector的数组vectorint adj[MAX_V]或者更现代地用vectorvectorpairint, int来同时存储邻居顶点和边权。#include vector using namespace std; const int MAX_V 100; // 方法1仅存储邻居顶点编号适用于无权图 vectorint adj_list[MAX_V]; // 方法2推荐存储 (邻居顶点编号, 边权值) 对适用于带权图 vectorvectorpairint, int weighted_adj_list(MAX_V); void addEdge(int from, int to, int weight) { // 对于无权图 adj_list[from].push_back(to); // 对于无向图还需要adj_list[to].push_back(from); // 对于带权图 weighted_adj_list[from].push_back({to, weight}); // 对于无向图还需要weighted_adj_list[to].push_back({from, weight}); } // 遍历顶点v的所有出边 void traverseNeighbors(int v) { cout Neighbors of vertex v : ; for (const auto neighbor : weighted_adj_list[v]) { cout - neighbor.first (weight: neighbor.second ) ; } cout endl; }邻接表的优缺点优点空间高效只存储实际存在的边空间复杂度为O(V E)对于稀疏图节省了大量内存。遍历邻居快遍历某个顶点的所有邻居时间复杂度与该顶点的度数邻居数成正比通常远小于O(V)。缺点查询边慢判断u到v是否有边需要遍历u的邻居列表最坏情况O(degree(u))。虽然可以用unordered_set存储邻居来将查询优化到平均O(1)但这会牺牲一些遍历效率和空间。实现稍复杂相比矩阵代码结构稍微复杂一点。实操心得在99%的算法竞赛和面试场景中邻接表是默认且首选的实现方式。因为它能高效处理大规模稀疏图而这是最常见的情况。只有在明确知道图非常稠密或者题目强制要求使用矩阵时才考虑邻接矩阵。我个人的代码模板库中vectorvectorpairint, int graph是绝对的主力。3. 关键概念辨析入边、出边与度的计算当我们处理有向图时边的方向赋予了顶点两种不同的“度”的概念这是理解很多算法如拓扑排序、欧拉路径的基础。出边从当前顶点指向其他顶点的边。顶点v的出度就是v的出边数量。在邻接表中graph[v].size()直接就是v的出度。入边从其他顶点指向当前顶点的边。顶点v的入度就是v的入边数量。计算入度需要遍历整个图。// 计算有向图中所有顶点的入度 vectorint calculateInDegree(int n, const vectorvectorpairint, int graph) { vectorint in_degree(n, 0); for (int u 0; u n; u) { for (const auto [v, w] : graph[u]) { // C17结构化绑定 in_degree[v]; // 对于每条 u-v 的边v的入度加1 } } return in_degree; } // 计算有向图中顶点v的出度非常简单 int outDegree(int v, const vectorvectorpairint, int graph) { return graph[v].size(); }为什么区分入度和出度很重要拓扑排序的经典Kahn算法就从入度为0的顶点开始。在网络流中源的出度与汇的入度是分析的基础。判断一个有向图是否存在欧拉回路条件就是每个顶点的入度等于出度。理解并熟练计算这两个概念是进行有向图算法分析的第一步。常见问题无向图的度对于无向图每条边(u, v)在邻接表中会被存储两次u的列表里有vv的列表里有u。因此顶点v的度就是graph[v].size()。同时无向图中顶点的度也等于其入度或出度因为无向边可以看作两条方向相反的有向边。4. 图的遍历深度与广度优先搜索遍历是图算法中最基础的操作如同数组的循环。两种最经典的遍历策略是深度优先搜索和广度优先搜索它们奠定了众多高级算法的思想基础。4.1 深度优先搜索一条路走到黑再回头DFS的策略是尽可能深地探索图的分支。它从某个顶点开始沿着一条边不断深入直到没有未访问的邻居然后回溯到上一个顶点探索另一条路径。这个过程天然适合用递归实现或者显式地使用栈。递归版DFS模板vectorbool visited; // 访问标记数组 void dfs(int v, const vectorvectorint graph) { visited[v] true; // 在这里处理顶点v例如打印、记录等 // cout v ; for (int neighbor : graph[v]) { if (!visited[neighbor]) { dfs(neighbor, graph); // 递归深入 } } // 回溯发生在这里函数返回时 } void dfsTraversal(int start, int n, const vectorvectorint graph) { visited.assign(n, false); dfs(start, graph); // 如果是非连通图可能需要循环检查所有顶点对未访问的调用dfs }迭代版DFS使用栈void dfsIterative(int start, const vectorvectorint graph) { int n graph.size(); vectorbool visited(n, false); stackint s; s.push(start); while (!s.empty()) { int v s.top(); s.pop(); if (visited[v]) continue; visited[v] true; // 处理顶点v // 注意为了与递归顺序一致在邻接表顺序下可能需要将邻居逆序入栈 for (int neighbor : graph[v]) { if (!visited[neighbor]) { s.push(neighbor); } } } }DFS的核心应用场景连通分量检测一次DFS能遍历一个连通子图的所有顶点。拓扑排序在有向无环图中。寻找图中的环。解决回溯问题如迷宫、八皇后图本身就是状态空间的模型。4.2 广度优先搜索层层推进由近及远BFS的策略是按距离起始点的层次来遍历。它先访问所有距离为1的邻居然后是距离为2的邻居依此类推。这保证了找到的路径在无权图中是最短路径。BFS必须使用队列来实现。BFS模板void bfs(int start, const vectorvectorint graph) { int n graph.size(); vectorbool visited(n, false); queueint q; visited[start] true; q.push(start); while (!q.empty()) { int v q.front(); q.pop(); // 处理顶点v for (int neighbor : graph[v]) { if (!visited[neighbor]) { visited[neighbor] true; // **关键**在入队时标记已访问避免重复入队 q.push(neighbor); } } } }BFS的核心应用场景无权图的最短路径BFS首次访问到某个顶点时经过的路径一定是最短路径。层次遍历例如在社交网络中寻找“二度好友”、“三度好友”。迷宫最短路径求解。广播消息模拟信息在网络中的传播过程。避坑技巧在BFS中必须在顶点入队时立即标记为已访问而不是在出队时。想象一下顶点A和B都是C的邻居它们会先后将C加入队列。如果在出队时才标记C就会被重复加入队列两次导致效率降低在复杂图中可能引发严重问题。这是新手最容易犯的错误之一。5. 最短路径算法从单源到全源寻找图中两点间的最短路径是图论最经典的问题之一。根据图的特性有无负权边和需求单源还是全源有不同的算法选择。算法核心思想时间复杂度适用图类型主要用途Dijkstra贪心每次从未确定顶点中选取距离源点最近的O((VE)logV) (优先队列)非负权有向/无向图单源最短路径Bellman-Ford动态规划松弛所有边 V-1 轮O(VE)任意权有向图可检测负权环单源含负权边SPFABF的队列优化只松弛被更新的顶点关联边平均O(kE)最坏O(VE)任意权有向图可检测负权环单源稀疏图负权Floyd-Warshall动态规划以每个顶点作为中转点更新距离O(V³)任意权有向/无向图可处理负权不能有负环全源最短路径5.1 Dijkstra算法非负权图的王者Dijkstra算法是解决单源、非负权图最短路径问题的标准算法。它的核心是维护一个“已确定最短距离”的集合并不断从“未确定”集合中挑选出当前距离源点最近的顶点加入“已确定”集合并松弛其出边。使用优先队列小顶堆优化的Dijkstra实现#include vector #include queue #include climits using namespace std; vectorint dijkstra(int start, int n, const vectorvectorpairint, int graph) { vectorint dist(n, INT_MAX); dist[start] 0; // 优先队列存储 (当前到该点的距离, 顶点编号) priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, start}); while (!pq.empty()) { auto [current_dist, u] pq.top(); // C17 pq.pop(); // 重要如果当前取出的距离大于记录的距离说明是旧的无用数据直接跳过 if (current_dist dist[u]) { continue; } for (const auto [v, weight] : graph[u]) { int new_dist dist[u] weight; if (new_dist dist[v]) { dist[v] new_dist; pq.push({new_dist, v}); // 可能产生重复数据但由上面的continue处理 } } } return dist; // dist[i] 即为从start到i的最短距离若为INT_MAX则不可达 }为什么Dijkstra不能处理负权边因为Dijkstra基于贪心策略假设“当前最短路径就是最终最短路径”。一旦有负权边这个假设就不成立了。因为可能通过一个当前距离更远的点加上一条负权边得到一条更短的路径。贪心策略无法回溯。5.2 Bellman-Ford与SPFA负权图的解决方案当图中存在负权边时就需要Bellman-Ford算法。它的思想很简单对所有的边进行V-1轮松弛操作。因为最短路径最多包含V-1条边所以V-1轮后所有最短路径必然被找到。如果在第V轮还能松弛说明图中存在从源点可达的负权环。Bellman-Ford标准实现struct Edge { int u, v, w; // 起点终点权值 }; bool bellmanFord(int start, int n, const vectorEdge edges, vectorint dist) { dist.assign(n, INT_MAX); dist[start] 0; // 松弛 n-1 轮 for (int i 0; i n - 1; i) { bool relaxed false; for (const auto e : edges) { if (dist[e.u] ! INT_MAX dist[e.u] e.w dist[e.v]) { dist[e.v] dist[e.u] e.w; relaxed true; } } if (!relaxed) break; // 如果一轮没有松弛提前结束 } // 检查第n轮是否还能松弛判断负环 for (const auto e : edges) { if (dist[e.u] ! INT_MAX dist[e.u] e.w dist[e.v]) { return false; // 存在从源点可达的负权环 } } return true; }SPFABellman-Ford的队列优化SPFA并不是一个“新算法”而是对Bellman-Ford的优化。它维护一个队列只对上一轮距离被更新过的顶点所关联的边进行松弛。在随机图上效率很高但最坏情况会退化成O(VE)。bool spfa(int start, int n, const vectorvectorpairint, int graph, vectorint dist) { dist.assign(n, INT_MAX); vectorint cnt(n, 0); // 记录入队次数用于检测负环 vectorbool inQueue(n, false); queueint q; dist[start] 0; q.push(start); inQueue[start] true; cnt[start]; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (const auto [v, w] : graph[u]) { if (dist[u] ! INT_MAX dist[u] w dist[v]) { dist[v] dist[u] w; if (!inQueue[v]) { q.push(v); inQueue[v] true; cnt[v]; if (cnt[v] n) { // 一个顶点入队超过n次说明有负环 return false; } } } } } return true; }实操心得在算法竞赛中如果题目明确没有负权边无脑用Dijkstra。如果可能有负权边且图是稀疏的可以尝试SPFA但要注意设置合理的入队次数限制以防被极端数据卡超时。如果题目要求检测负环或者图比较稠密老老实实用标准的Bellman-Ford更稳妥。6. 最小生成树连接所有点的最低成本想象你要在几个村庄之间铺设电线让所有村庄都通电且总电线长度最短。这就是最小生成树问题。MST要求在一个连通无向带权图中找到一个边的子集使得这些边连接所有顶点且没有环并且总权重最小。两个最著名的算法是Prim和Kruskal。6.1 Prim算法从一点开始逐步生长Prim算法非常像Dijkstra。它从任意一个顶点开始每次将连接“已选顶点集合”和“未选顶点集合”的权值最小的边及其连接的顶点加入MST。使用优先队列的Prim算法实现int prim(int n, const vectorvectorpairint, int graph) { vectorbool inMST(n, false); priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; // 从顶点0开始 pq.push({0, 0}); // (边权, 顶点) int mst_weight 0; int edges_used 0; while (!pq.empty() edges_used n) { auto [weight, u] pq.top(); pq.pop(); if (inMST[u]) continue; // 已经在MST中跳过 inMST[u] true; mst_weight weight; edges_used; for (const auto [v, w] : graph[u]) { if (!inMST[v]) { pq.push({w, v}); // 将与u相连的、不在MST中的顶点加入队列 } } } // 如果 edges_used ! n说明图不连通无法生成MST return (edges_used n) ? mst_weight : -1; }6.2 Kruskal算法按权值排序避免成环Kruskal算法的思路更直接将所有边按权值从小到大排序然后依次考虑每条边。如果加入这条边不会在已选的边集中形成环就加入它直到选中了n-1条边。判断是否成环需要用到并查集这个高效的数据结构。Kruskal算法实现需并查集支持struct DSU { vectorint parent, rank; DSU(int n) : parent(n), rank(n, 1) { for (int i 0; i n; i) parent[i] i; } int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); // 路径压缩 } bool unite(int x, int y) { x find(x); y find(y); if (x y) return false; if (rank[x] rank[y]) swap(x, y); // 按秩合并 parent[y] x; if (rank[x] rank[y]) rank[x]; return true; } }; int kruskal(int n, vectortupleint, int, int edges) { // (weight, u, v) sort(edges.begin(), edges.end()); // 按权值排序 DSU dsu(n); int mst_weight 0; int edges_used 0; for (const auto [w, u, v] : edges) { if (dsu.unite(u, v)) { // 如果u和v不在一个集合加入这条边不会成环 mst_weight w; edges_used; if (edges_used n - 1) break; } } return (edges_used n - 1) ? mst_weight : -1; }Prim vs Kruskal 如何选择Prim算法更适合稠密图。它的时间复杂度与使用邻接矩阵还是邻接表有关用优先队列优化后是O(ElogV)。在边非常多的时候其性能相对稳定。Kruskal算法更适合稀疏图。它的时间复杂度主要花在排序上为O(ElogE)。在边比较少的时候排序开销小且实现非常简洁尤其是借助并查集。7. 拓扑排序为有向无环图的任务排个序当你有一系列有依赖关系的任务比如编译源码、课程选修你需要找到一个线性序列使得对于任何有向边(u-v)u都排在v的前面。这就是拓扑排序它只适用于有向无环图。7.1 Kahn算法基于入度的广度优先策略这是最直观的算法。不断寻找图中入度为0的顶点将其输出并从图中“移除”将其所有出边指向的顶点入度减1。重复此过程。vectorint topologicalSortKahn(int n, const vectorvectorint graph) { vectorint in_degree(n, 0); for (int u 0; u n; u) { for (int v : graph[u]) { in_degree[v]; } } queueint q; for (int i 0; i n; i) { if (in_degree[i] 0) { q.push(i); } } vectorint topo_order; while (!q.empty()) { int u q.front(); q.pop(); topo_order.push_back(u); for (int v : graph[u]) { if (--in_degree[v] 0) { q.push(v); } } } // 如果排序后的顶点数小于n说明图中有环 if (topo_order.size() ! n) { return {}; // 返回空数组表示无法拓扑排序存在环 } return topo_order; }7.2 基于DFS的拓扑排序另一种方法是在DFS回溯的过程中将顶点加入序列。最终将序列反转即可。这种方法更容易在递归中集成其他逻辑。bool dfsTopo(int u, vectorint visited, const vectorvectorint graph, vectorint order) { visited[u] 1; // 1表示正在访问中 for (int v : graph[u]) { if (visited[v] 1) return false; // 存在环 if (visited[v] 0) { if (!dfsTopo(v, visited, graph, order)) return false; } } visited[u] 2; // 2表示已访问完成 order.push_back(u); return true; } vectorint topologicalSortDFS(int n, const vectorvectorint graph) { vectorint visited(n, 0); // 0未访问1访问中2已结束 vectorint order; for (int i 0; i n; i) { if (visited[i] 0) { if (!dfsTopo(i, visited, graph, order)) { return {}; // 检测到环 } } } reverse(order.begin(), order.end()); // 反转得到拓扑序 return order; }拓扑排序的应用远不止任务调度编译顺序确定源文件编译的先后顺序。课程安排安排有先修课要求的课程。依赖解析软件包管理器确定安装顺序。死锁检测如果图中有环则说明存在循环依赖可能引发死锁。8. 常见问题与排查技巧实录在实际编码和解题中总会遇到一些“坑”。这里记录了几个最常见的问题和我的解决思路。8.1 图不连通导致遍历不完全无论是DFS还是BFS如果只从一个起点开始对于非连通图只能访问到该连通分量里的顶点。标准做法是初始化访问数组后用一个循环遍历所有顶点对每个未访问的顶点调用遍历函数。void traverseWholeGraph(int n, const vectorvectorint graph) { vectorbool visited(n, false); int componentCount 0; // 连通分量计数器 for (int i 0; i n; i) { if (!visited[i]) { // bfs(i, graph, visited); 或 dfs(i, graph, visited); componentCount; } } cout Number of connected components: componentCount endl; }8.2 递归深度过大导致栈溢出DFS的递归实现简洁但当图深度很大例如一条长链时可能导致递归调用栈溢出。解决方案改用迭代版DFS显式栈。调整编译器的栈空间大小竞赛中通常不可行。对于明确是深度搜索的问题考虑是否能用BFS解决。8.3 邻接表遍历时修改容器这是一个非常隐蔽的错误。在遍历vectorint adj[v]时如果调用的函数比如递归的DFS可能会向adj[v]中添加新的边例如在遍历过程中动态建图就会导致迭代器失效引发未定义行为。// 危险代码示例 void dfs_bad(int v, vectorvectorint graph) { visited[v] true; for (int to : graph[v]) { // 遍历过程中如果dfs递归调用修改了graph[v]这里会出错 if (!visited[to]) { // 假设这里某种条件下会调用 addEdge(graph, v, some_new_node); dfs_bad(to, graph); } } }安全做法如果需要遍历的同时修改可以先复制一份邻居列表或者使用索引遍历。void dfs_safe(int v, vectorvectorint graph) { visited[v] true; // 复制当前邻居列表 vectorint neighbors graph[v]; for (int to : neighbors) { if (!visited[to]) { // 现在可以安全地修改graph[v]了 dfs_safe(to, graph); } } }8.4 多测试用例未重置数据在在线判题系统中通常有多个测试用例。如果你使用全局或静态的graph、visited、dist等数组必须在每个测试用例开始前将其彻底重置。忘记清空是常见的WA错误答案原因。void solve() { int n, m; while (cin n m) { // 1. 重置图结构 vectorvectorpairint, int graph(n); // 2. 读入数据建图... // 3. 重置辅助数组 vectorint dist(n, INF); vectorbool visited(n, false); // 4. 执行算法... } }8.5 负权环的误判与处理在使用SPFA或Bellman-Ford判断负环时需要注意从特定源点出发标准Bellman-Ford和上面的SPFA只能检测从源点s出发可达的负权环。如果图不连通且负环存在于另一个连通分量中这些算法会报告“无负环”但这不意味着整个图没有负环。全图检测为了检测整个图中的任何负环一个常用的技巧是初始化一个超级源点。即创建一个新顶点将其到所有原顶点的距离设为0然后从这个超级源点跑SPFA/Bellman-Ford。或者更简单粗暴地在SPFA开始时将所有顶点入队并标记。// SPFA检测全图负环通用做法 bool hasNegativeCycle(int n, const vectorvectorpairint, int graph) { vectorint dist(n, 0); // 初始距离设为0 vectorint cnt(n, 0); vectorbool inQueue(n, true); // 所有顶点一开始都在队列中 queueint q; for (int i 0; i n; i) q.push(i); while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (const auto [v, w] : graph[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; if (!inQueue[v]) { q.push(v); inQueue[v] true; if (cnt[v] n) { return true; // 发现负环 } } } } } return false; }图论这一章的内容就像一座宝库从基础的存储遍历到经典的最短路径、最小生成树再到拓扑排序每一部分都对应着大量经典的现实问题。理解概念是第一步更重要的是动手实现并在大量的练习中体会不同算法之间的微妙差别和适用场景。我建议从邻接表的实现、DFS/BFS遍历模板开始牢牢掌握然后逐个攻破Dijkstra、并查集Kruskal、拓扑排序这些高频考点。当你遇到一个复杂的问题能下意识地想到“这可以建模成图用那个算法来解决”时这一章才算真正学到位了。