
如果你只把图当成“邻接表DFS/BFS”那这篇文章就是为你准备的前言图是数据结构家族中最接近真实世界模型的结构。社交网络的好友关系、地图导航的路线规划、编译器的依赖分析、神经网络的计算图……背后都是图。然而很多同学学完图之后只记住了两个遍历甚至分不清“十字链表”和“邻接多重表”的区别。本文将彻底硬核地梳理图数据结构的方方面面5种存储结构、3种遍历变体、4大经典算法以及它们的工程级实现细节。全文约8000字建议先收藏。一、图的基本概念——别在基础上模糊1.1 定义与术语图 G(V,E)G(V,E) 由顶点集 VV 和边集 EE 组成。有向图 vs 无向图边是否有方向。带权图每条边附有权值如距离、代价。简单图无自环、无重边。绝大多数算法针对简单图。完全图任意两点间都有边。无向完全图边数为 n(n−1)/2n(n−1)/2有向为 n(n−1)n(n−1)。稀疏图 vs 稠密图边界模糊通常 ∣E∣≪∣V∣2∣E∣≪∣V∣2 为稀疏反之为稠密。存储结构的选择由此决定。1.2 度、入度、出度无向图度 邻居数。有向图入度指向自己的边数、出度指出去的边数。总入度 总出度 |E|。1.3 路径与连通路径顶点序列相邻顶点有边。简单路径顶点不重复。环起点终点的路径。连通图无向任意两点可达。连通分量极大连通子图。强连通图有向任意两点互相可达。强连通分量SCC极大强连通子图。弱连通将有向边视为无向后连通。面试点如何用O(VE)求无向图的连通分量数 DFS/BFS即可。如何求有向图的强连通分量 见后文Kosaraju/Tarjan。二、存储结构——选错结构算法白写2.1 邻接矩阵实现bool adj[n][n]或int weight[n][n]。cpp复制下载// 无向带权图INF表示无边 int G[MAXN][MAXN]; memset(G, 0x3f, sizeof(G)); // 初始化为无穷大 G[u][v] w; G[v][u] w; // 无向需对称空间O(V2)O(V2)对稠密图友好E≈V2E≈V2稀疏图极浪费。时间判断两点邻接 O(1)获取所有邻居 O(V)——即使只有2个邻居也要扫描整行。使用场景Floyd算法、传递闭包、极稠密图。优化技巧用bitset压位空间降为 V2/64V2/64且支持快速的按位运算如求两行交集计算公共邻居。2.2 邻接表实现vectorint adj[n]无向图对称添加。cpp复制下载vectorpairint, int adj[MAXN]; // (邻居, 权重) adj[u].emplace_back(v, w); adj[v].emplace_back(u, w);空间O(VE)O(VE)稀疏图首选。时间遍历所有邻居 O(deg(u))判断 u-v 是否有边需要遍历邻接表最坏 O(V) → 可改用unordered_set但空间翻倍。变体链式前向星静态数组版竞赛常客比vector快。cpp复制下载int head[N], to[M], nxt[M], w[M], cnt 0; void add(int u, int v, int val) { to[cnt] v; w[cnt] val; nxt[cnt] head[u]; head[u] cnt; } // 遍历 for(int i head[u]; i; i nxt[i]) { int v to[i]; }2.3 十字链表 —— 有向图专用背景邻接表只能高效遍历出边无法快速遍历入边。十字链表将出边表和入边表融合。节点结构text复制下载// 顶点节点 data; firstin; firstout; // 边节点 tailvex, headvex; // 尾顶点索引、头顶点索引 hlink; // 下一个同入度的边即 headvex 相同的边 tlink; // 下一个同出度的边即 tailvex 相同的边 weight;图解每个顶点维护两个指针firstout以该顶点为尾的第一条边和firstin以该顶点为头的第一条边。每条边节点同时出现在“出边链表”和“入边链表”中通过tlink和hlink。复杂度空间 O(VE)找入边/出边都是 O(deg)。实现稍复杂但拓扑排序、求强连通分量等需要反向边的场景很合适。2.4 邻接多重表 —— 无向图的高效存储问题无向图用邻接表存时一条边需要存两次u→v 和 v→u修改/删除边时需要找另一条“对称边”效率低。邻接多重表让一条边只对应一个节点。边节点结构text复制下载mark; // 是否被访问过 ivex, jvex; // 两个顶点 ilink; // 依附于 ivex 的下一条边 jlink; // 依附于 jvex 的下一条边 weight;顶点节点firstedge指向第一条依附于该顶点的边。特点删除边时通过ilink和jlink可以 O(1) 找到同顶点的其他边无需遍历两条邻接表。常用于需要频繁增删边的无向图算法如求欧拉回路时的 Hierholzer 算法。2.5 边集数组实现vectortupleint,int,int edges每条边存 (u, v, w)。空间O(E)但无法快速判断邻接关系。仅用于 Kruskal 最小生成树算法因为只需对所有边排序。三、图的遍历——基础但处处是细节3.1 DFS深度优先搜索递归版cpp复制下载bool vis[N]; void dfs(int u) { vis[u] true; for(auto [v, w] : adj[u]) if(!vis[v]) dfs(v); }迭代版防止栈溢出cpp复制下载stackint st; st.push(s); vis[s] true; while(!st.empty()) { int u st.top(); st.pop(); // 注意需在入栈时标记已访问否则会重复入栈 for(auto [v, w] : adj[u]) if(!vis[v]) { vis[v] true; st.push(v); } }应用求连通分量拓扑排序后序 DFS 逆序检测环无向图遇到已访问且非父节点则有环有向图需额外onStack数组二分图判定染色法3.2 BFS广度优先搜索cpp复制下载queueint q; q.push(s); vis[s]true; while(!q.empty()) { int u q.front(); q.pop(); for(auto v : adj[u]) if(!vis[v]) { vis[v] true; q.push(v); // 求无权最短路时dist[v] dist[u] 1 } }应用无权图最短路Dijkstra 退化为 BFS层次遍历二叉树已不新鲜图的 BFS 树可求各层节点双向 BFS减少状态爆炸3.3 遍历的硬核优化位集加速当图以邻接矩阵存储时BFS 的“找未访问邻居”可以用bitset加速。cpp复制下载bitsetN vis, cur, next; cur adj[s]; // adj[s] 是一个 bitset表示 s 的邻居 while(!cur.none()) { next.reset(); for(int u cur._Find_first(); u ! cur.size(); u cur._Find_next(u)) { // 访问节点 u next | adj[u]; } next ~vis; // 去除已访问 vis | next; cur next; }复杂度从 O(V^2) 降为 O(V^3/64)实际加速明显。四、经典算法——从理论到工程4.1 最小生成树MSTPrim 算法适合稠密图O(V^2) 或 O(E log V)维护dist[]表示节点到当前生成树的最短边。每次选最小dist加入树并更新邻居的dist。用优先队列优化O(E log V)。Kruskal 算法适合稀疏图O(E log E)边集排序用并查集判断是否形成环。关键对比Prim 处理连通图Kruskal 生成森林时天然处理多分量。代码Kruskal核心cpp复制下载sort(edges.begin(), edges.end()); DSU dsu(n); int total 0, cnt 0; for(auto [w, u, v] : edges) { if(dsu.unite(u, v)) { total w; cnt; if(cnt n-1) break; } }4.2 最短路径算法时间复杂度特点BFSO(VE)仅限无权图或权值相同DijkstraO((VE) log V) 或 O(V^2)非负权单源最优Bellman-FordO(VE)可负权检测负环SPFA最坏 O(VE) 平均 O(kE)可负权容易被卡FloydO(V^3)全源最短可负权无负环Dijkstra 的堆优化实现注意不能处理负权cpp复制下载vectorint dist(n, INF); dist[s] 0; priority_queuepairint,int, vector..., greater... pq; pq.emplace(0, s); while(!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if(d ! dist[u]) continue; // 过期节点跳过 for(auto [v, w] : adj[u]) { if(dist[v] dist[u] w) { dist[v] dist[u] w; pq.emplace(dist[v], v); } } }Floyd 算法动态规划全源cpp复制下载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必须在最外层这是“中间节点”阶段的思想。可用于传递闭包将加法改为逻辑与取 min 改为或。4.3 拓扑排序有向无环图 DAGKahn 算法BFS 式cpp复制下载int indeg[n]; queueint q; for(int i 0; i n; i) if(indeg[i]0) q.push(i); vectorint topo; while(!q.empty()) { int u q.front(); q.pop(); topo.push_back(u); for(auto v : adj[u]) if(--indeg[v] 0) q.push(v); } if(topo.size() ! n) // 有环DFS 式cpp复制下载vectorint order; vectorint status; // 0未访1访问中2完成 bool dfs(int u) { status[u] 1; for(int v : adj[u]) { if(status[v] 1) return false; // 发现后向边-有环 if(status[v] 0 !dfs(v)) return false; } status[u] 2; order.push_back(u); return true; } // 最后 reverse(order) 得到拓扑序4.4 强连通分量SCCKosaraju 算法两次 DFS好理解对原图 DFS 得到后序时间戳类似拓扑序。将图转置所有边反向。按时间戳从大到小对转置图 DFS每个 DFS 树就是一个 SCC。Tarjan 算法一次 DFS性能更高cpp复制下载int dfn[N], low[N], sta[N], top, insta[N], scc_id[N], scc_cnt, timestamp; void tarjan(int u) { dfn[u] low[u] timestamp; sta[top] u; insta[u] 1; for(int v : adj[u]) { if(!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if(insta[v]) low[u] min(low[u], dfn[v]); } if(dfn[u] low[u]) { scc_cnt; int v; do { v sta[top--]; insta[v] 0; scc_id[v] scc_cnt; } while(v ! u); } }应用缩点将 SCC 缩成一个 DAG、2-SAT 问题。五、进阶与工程实践5.1 差分约束系统形式为 xi−xj≤cxi−xj≤c 的不等式组可转化为图论对每个约束建边j - i权值c然后跑最短路存在负环则无解。常见技巧添加超级源点与所有点连权 0 保证连通性。5.2 欧拉路径/回路一笔画问题无向图欧拉回路所有顶点度为偶数。无向图欧拉路径恰有 0 或 2 个奇度顶点。Hierholzer 算法DFS删除边 O(E) 构造路径。cpp复制下载void hierholzer(int u) { while(!adj[u].empty()) { int v adj[u].back(); adj[u].pop_back(); // 需支持高效删边 // 如果是无向图还需要删掉 v 邻接表中的 u多重表可优化 hierholzer(v); } path.push_back(u); } // 最后 reverse(path)5.3 网络流问题最大流/最小割Ford-Fulkerson方法 DFS 的 Edmonds-Karp O(VE^2) 太慢。Dinic算法 O(E√V) 或 O(V^2E)实际很快。核心BFS 建层次图DFS 多路增广。常用技巧拆点点容量转边容量、超级源汇。5.4 在数据库与图数据库中的应用现代图数据库Neo4j、JanusGraph的底层存储多采用邻接表 索引或列族存储。索引是查询加速的核心无索引邻接每个节点存储邻居列表遍历需扫描所有边。索引邻接每个节点带指向邻居的指针O(1) 访问。面试常问在 10 亿节点、100 亿边的社交图中如何存储能使“共同好友”查询最快答案使用邻接矩阵分块压缩或基于 bitmap 的 CSB 树。六、复杂度与选择指南操作需求推荐存储原因频繁判断两点是否邻接邻接矩阵O(1)边数极少 ( 1000V)邻接表空间省遍历快有向图需要频繁入边/出边十字链表双向 O(1) 定位无向图频繁增删边邻接多重表单边存储只做 Kruskal边集数组排序友好竞赛暴力链式前向星常数最小结语图不是单个数据结构而是一整个“工具箱”。从最简单的邻接表到复杂的 Tarjan每种结构都是对特定场景的极致适配。很多人在刷完 LeetCode 的numIslands后就觉得图“学会了”但真正硬核的地方在于你能否用bitset优化 BFS能否手写链式前向星能否用 Tarjan 求强连通分量能否在项目中选择最合适的存储结构希望这篇文章能帮你从“会用图”走到“驾驭图”。如果你觉得有收获请点赞、收藏、转发让更多同学看到硬核的内容。