数据结构里最容易被低估的其实是图Graph这一块。很多人学链表、栈、队列的时候还好一到“图的基本操作C/C代码实现”就开始犯迷糊又是矩阵又是链表还有DFS、BFS各种遍历顺序。但说句实话图反而是和现实世界联系最紧密的数据结构——朋友圈好友推荐、地铁换乘路线、编译器的任务依赖、网络里的路由跳数这些底层建模全是图。而图的基本操作就是所有图论算法最短路径、最小生成树、拓扑排序的入场券建图和遍历做不熟后面基本寸步难行。这篇文章适合正在学数据结构/算法的学生、准备考研机试的人、想手撕图论题的面试候选人。我尽量不写教科书那种“第1步做什么、第2步做什么”的冰冷提纲而是直接把C/C实现过程中的选型逻辑、代码细节、踩过的坑摊开讲。你能拿到的是可以在自己的编译器里直接跑起来、并且能理解为什么这么写的完整代码。1. 图的存储到底怎么选邻接矩阵和邻接表的取舍1.1 邻接矩阵一张二维表承载全部关系邻接矩阵的思路非常直白假设图里有 N 个顶点就开一个 N×N 的二维数组。matrix[i][j] 为 1或者权值表示顶点 i 到顶点 j 存在边为 0 表示没有边。对于无向图因为边没有方向所以 matrix[i][j] 和 matrix[j][i] 必须同时为 1整个矩阵关于主对角线对称。这个结构很像班级里的“座位邻座表”如果同学 A 和同学 B 是同桌那就在第 A 行第 B 列打个勾同时第 B 行第 A 列也打个勾。你想知道任意两个人是不是同桌直接看对应格子即可都不用数。这个方案最大的优点是判断任意两个顶点之间是否有边时间复杂度是 O(1)代码实现也最贴近人的直觉。所以我自己带新人写图的代码时第一版永远建议先用邻接矩阵跑通别上来就整邻接表加指针。矩阵方式在顶点数量不大比如 N ≤ 2000的场景配合 Floyd-Warshall 这类多源最短路算法反而比邻接表舒服很多。缺点呢也很明显空间复杂度恒为 O(N²)。如果图里有 1 万个顶点矩阵就要开 1 亿个元素按照 int 占 4 字节算大约是 400MB 内存这在大多数在线评测系统和普通项目里已经算非常夸张的消耗了。如果用 10 万个顶点理论上需要的空间直接到 40GB根本不可能这样写。1.2 邻接表只为真实存在的边分配空间邻接表的设计更“抠门”不再给不存在的边预留位置而是为每个顶点维护一个“邻居列表”只有真实存在边的两个顶点之间才产生记录。你想象一下一个人想知道自己有哪些朋友不会去翻一本包含全国所有人名字的花名册而是直接打开自己手机里的通讯录列表里存的都是真实联系人。邻接表就是这种“通讯录思维”。具体到 C/C 实现我通常用 vectorvector 外层 vector 的长度等于顶点数 N内层每个 vector 存这个顶点能到达的邻居编号。如果想表示带权图就把内层元素换成一个结构体 Edge里面包含 to 和 weight 两个字段。邻接表在无向图中的一条边会被存储两次分别挂在两个端点下在有向图中只存一次挂在起点下。邻接表的优势是空间 O(NM)其中 M 是边数遍历某个顶点的所有邻居只需要 O(度数)这在处理大规模稀疏图时非常关键。社交媒体的好友关系就是典型的稀疏图——一个人认识的好友数量通常远小于全网用户数用邻接表存储显然更合理。我整理了个对比表方便记对比项邻接矩阵邻接表判断 u、v 是否有边O(1)O(degree(v))个别实现可优化到 O(log degree)遍历某顶点的全部邻居O(N)O(degree(v))空间复杂度O(N²)O(NM)删除一条边O(1) 赋值即可需要链表/vector 查找删除适合场景稠密图、小规模验证、Floyd稀疏图、大规模图、Dijkstra/DFS 等场景1.3 带权图怎么存先把未来要用的路铺好很多教材在讲图的基本操作时默认只讲无权图矩阵里存 0/1链表节点里只放顶点编号。但实际做题和工程项目中带权图才是常态——地铁票价就是边的权重公路里程也是。如果不提前把带权图的存法搞清楚后面学 Dijkstra、Prim 时还得回过头来改结构反而更折腾。所以我在自己的代码模板里一般直接按带权图设计。邻接矩阵的带权写法是matrix[i][j] 存权值用 0 表示“没有边”但如果某些边的合法权值可能为 0那就得换成用极大值 INF 表示不连通。比较经典的 INF 取法是 0x3f3f3f3f这个数字约等于 10 亿足够大而且两个 0x3f3f3f3f 相加也不会溢出 int 上限属于算法竞赛里常用的技巧。邻接表带权写法则是在 Edge 结构里加一个 weight 字段struct Edge { int to; int weight; Edge(int t, int w) : to(t), weight(w) {} };这里有个新手特别容易踩的坑无向图插入一条边时记得要 push 两次分别把 u-v 和 v-u 都加进去。我见过好多同学只 push 一次结果遍历的时候发现图是“半连通”的从 0 出发能到 1但从 1 出发就找不到 0排查半天才发现无向边漏了反向。2. 核心操作与遍历原理这些代码为什么要这么写2.1 建图与边操作初始化决定命运图的基本操作包括创建图、插入边、删除边、判断边是否存在以及最重要的遍历。先说建图和边操作。邻接矩阵版在建图时第一步是初始化把所有元素清 0无权图或清 INF带权图。很多人会忽略这一步直接用默认未初始化的数组结果里面全是随机值一判断“是否存在边”就出错。C 里如果容器选的是 vectorvector matrix(n, vector (n, 0))构造传第二个参数就能直接完成清零这比 C 语言里用 memset 要顺手不少。插入边的操作对无权无向图来说就是void addEdge(int u, int v) { matrix[u][v] 1; matrix[v][u] 1; }删除边也很直接把这两个位置重新赋 0 即可。邻接矩阵的优势在这里体现得很明显判断两个点是否有边、添加边、删除边都是 O(1)代码可读性极强。如果是带权图addEdge 还要多传一个 weight 参数内部把赋值 1 改成赋值 weight。删除边时如果是带权图且约定 INF 表示不连通就赋 INF。对于邻接表版addEdge 就是 vector 的 push_back。无向图是 adj[u].push_back(v)、adj[v].push_back(u)。这个操作看起来简单但有一点值得提如果题目不允许存在重边那 addEdge 之前还得先检查这条边是不是已经存在。用 vector 存储时检查成本较高所以很多严格要求不能重边的题我会直接用 vectorunordered_set 来替代最外层加内层或者读入完成后做一次排序去重。普通学习和基本遍历场景vector 就够用不用过度设计。2.2 DFS一头扎到底的回溯策略深度优先搜索DFS是所有图操作里最需要直觉的一个。你可以想象自己在走一个地宫从入口进去后看到岔路就随便选一条走一直往前走直到前方没路了再退回上一个岔路口换另一条没试过的路继续。这个过程翻译成代码就是递归进入一个顶点后先标记这个顶点已经访问过再依次对“没有被访问过的邻居”递归调用 DFS。有人会问为什么非要记录 visited因为图里存在环。如果不做标记DFS 在环里会无限循环从一个顶点出发绕一圈又回到自己然后继续绕永远停不下来。树结构天然没有环所以树的遍历不需要 visited图必须加这道保险。这个区别我建议你在纸上画一个有环图然后不带 visited 跟一遍代码亲眼看看系统栈怎么被塞爆的记忆会非常深刻。为了好理解给出最朴素的 DFS 伪代码框架dfs(v): 标记 v 已访问 输出或处理 v 对 v 的每个邻居 next: 如果 next 未被访问: dfs(next)递归代码与这个框架几乎一一对应写起来很自然。我建议初学者先接受这个递归版本因为它的逻辑最贴近“回溯”这个原始想法。等你能熟练画出递归调用栈之后再考虑改成显式栈的非递归版本那个主要是为了规避大图递归爆栈的问题后面在常见问题章节我会专门展开。2.3 BFS一圈一圈往外推的扩散策略广度优先搜索BFS的思路完全相反它不再追求“一条路走到底”而是像往平静的水面扔一颗石子波纹一圈一圈往外扩散。从起点出发先访问所有距离为 1 的邻居再访问所有距离为 2 的邻居依次类推。要实现这种“先遇到的先处理”的顺序就必须用到队列queue这个先进先出的结构。BFS 的框架也不复杂bfs(start): 初始化空队列 q 将 start 入队并标记已访问 只要队列不空: 取出队首 cur 输出或处理 cur 对 cur 的每个邻居 next: 如果 next 未被访问: 将 next 入队并标记已访问这里有一个非常关键的细节值得所有初学者盯住入队的时候就要立刻标记 visited而不是等弹出的时候再标记。我自己早期写 BFS 就吃过这个亏——如果出队时才标记队列里可能会被推入很多个重复顶点。举个例子顶点 A 同时连接 B、C、D而 B、C、D 又都连接到 E那么在扩展第二层时E 有可能被 B、C、D 各入队一次。如果你在弹出时才标记队列里会出现三个 E遍历结果不仅重复还会破坏“一层层推进”的顺序严重时在带层数的题目里计算出错。BFS 还有一个很有价值的性质在无权图中从起点到某个顶点的第一次访问走的路径一定是最短路径按边数计。因为 BFS 是按距离逐层扩展的当某个顶点第一次被访问时它所在的层数就是起点到它的最短边数。如果需要在输出路径时回溯可以额外维护一个 parent 数组记录每个顶点第一次是被哪个顶点发现的最后从终点沿着 parent 一路指回起点就能还原整条最短路径。2.4 连通分量判断遍历的一个高频延伸学会了 DFS/BFS很多操作其实可以直接建立在它们之上。比如判断无向图中有多少个连通分量——也就是图里有多少个“互不相连的岛屿”。思路很简单循环遍历所有顶点只要某个顶点还没被访问过就以它为起点做一次 DFS 或 BFS同时把连通分量计数器加 1。因为一次完整的遍历会走完当前顶点所在的整个连通块所以这个计数就是最终答案。例如有一个社交网络里面可能同时存在好几个互不认识的“圈子”连通分量数就是圈子的数量。类似的判断从 u 能不能到达 v等价于从 u 做一次 DFS/BFS结束后检查 visited[v] 是否为 true。这些延伸都是基本操作的直接应用也是面试中“岛屿数量”这类题型的原始模型。3. 完整可运行的图操作代码两种存储四套遍历3.1 邻接矩阵版完整实现适合快速验证思路我先把邻接矩阵版完整代码贴出来。代码结构是一个简单的 C 类包含初始化、加边、判断边、DFS、BFS 和连通分量计数。你可以直接复制到本地编译器跑。#include iostream #include vector #include queue using namespace std; class GraphMatrix { private: int n; // 顶点个数 vectorvectorint matrix; // 邻接矩阵 vectorbool visited; // 访问标记 void dfsCore(int v) { visited[v] true; cout v ; // 从小到大遍历邻居保证输出稳定 for (int u 0; u n; u) { if (matrix[v][u] !visited[u]) { dfsCore(u); } } } public: GraphMatrix(int vertexCount) { n vertexCount; matrix.resize(n, vectorint(n, 0)); visited.resize(n, false); } void addEdge(int u, int v) { if (u 0 || u n || v 0 || v n) return; matrix[u][v] 1; matrix[v][u] 1; // 无向图需要对称赋值 } void removeEdge(int u, int v) { if (u 0 || u n || v 0 || v n) return; matrix[u][v] 0; matrix[v][u] 0; } bool hasEdge(int u, int v) { return matrix[u][v] 1; } void dfs(int start) { fill(visited.begin(), visited.end(), false); cout DFS from start : ; dfsCore(start); cout endl; } void bfs(int start) { fill(visited.begin(), visited.end(), false); queueint q; visited[start] true; q.push(start); cout BFS from start : ; while (!q.empty()) { int cur q.front(); q.pop(); cout cur ; for (int u 0; u n; u) { if (matrix[cur][u] !visited[u]) { visited[u] true; q.push(u); } } } cout endl; } int countComponents() { fill(visited.begin(), visited.end(), false); int cnt 0; for (int v 0; v n; v) { if (!visited[v]) { cnt; dfsCore(v); // 这里会把当前连通块全部标记 } } return cnt; } }; int main() { // 构造一个 7 个顶点的无向图 // 0-1, 0-2, 1-3, 1-4, 2-5, 2-6 GraphMatrix g(7); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(1, 4); g.addEdge(2, 5); g.addEdge(2, 6); g.dfs(0); // 预期输出: 0 1 3 4 2 5 6 g.bfs(0); // 预期输出: 0 1 2 3 4 5 6 return 0; }运行这个程序DFS 从 0 出发的访问序列是“0 1 3 4 2 5 6”BFS 从 0 出发的序列是“0 1 2 3 4 5 6”。为什么 BFS 的输出如此“规则”因为它严格按层推进第 1 层是 1、2第 2 层是 3、4、5、6。对比着看这两个序列能帮你建立对“深度优先和广度优先”的直观认识。3.2 邻接表版完整实现应对大规模图如果图的规模上升或者边的数量远小于 N²建议把代码切换成邻接表。下面的类逻辑和矩阵版几乎一样只是存储结构从 vectorvector matrix 换成了 vectorvector adj方法名保持统一方便你对照迁移。#include iostream #include vector #include queue using namespace std; struct Edge { int to; int weight; Edge(int t, int w 1) : to(t), weight(w) {} }; class GraphAdj { private: int n; vectorvectorEdge adj; // 邻接表 vectorbool visited; void dfsCore(int v) { visited[v] true; cout v ; for (const Edge e : adj[v]) { int u e.to; if (!visited[u]) { dfsCore(u); } } } public: GraphAdj(int vertexCount) { n vertexCount; adj.resize(n); visited.resize(n, false); } void addEdge(int u, int v, int w 1) { adj[u].push_back(Edge(v, w)); adj[v].push_back(Edge(u, w)); // 无向图添加反向边 } void dfs(int start) { fill(visited.begin(), visited.end(), false); cout DFS from start : ; dfsCore(start); cout endl; } void bfs(int start) { fill(visited.begin(), visited.end(), false); queueint q; visited[start] true; q.push(start); cout BFS from start : ; while (!q.empty()) { int cur q.front(); q.pop(); cout cur ; for (const Edge e : adj[cur]) { int u e.to; if (!visited[u]) { visited[u] true; q.push(u); } } } cout endl; } int countComponents() { fill(visited.begin(), visited.end(), false); int cnt 0; for (int v 0; v n; v) { if (!visited[v]) { cnt; dfsCore(v); } } return cnt; } };注意这里的 addEdge 带了一个默认参数 w 1也就是说不传权值的时候仍按无权图处理传权值就成为带权图。这个默认参数技巧在刷题时很省事你不需要在无权和带权之间来回改接口。3.3 如果想用纯 C 实现怎么改虽然标题写的是 C/C但不少同学的课程实验要求用纯 C 完成。C 语言没有 class、vector、引用写起来确实繁琐一点但核心框架可以平移。邻接矩阵版最直接#define MAXV 100 int graph[MAXV][MAXV]; int visited[MAXV]; void addEdge(int u, int v) { graph[u][v] 1; graph[v][u] 1; } void dfs(int v, int n) { visited[v] 1; printf(%d , v); for (int u 0; u n; u) { if (graph[v][u] !visited[u]) { dfs(u, n); } } }邻接表版就需要手写链表了。经典做法是两个结构体一个是边节点 ArcNode存邻居编号和指向下一条边的指针另一个是顶点表头 VNode存顶点数据和头指针。加边时用头插法把新节点插到链表头部。麻烦的地方在于所有节点都要 malloc程序结束前还要遍历链表逐个 free忘掉释放会内存泄漏。如果你只是做课程实验用邻接矩阵的 C 版本最不容易出错如果需要在纯 C 下处理大规模图那就要老老实实把链表的增删查写对。4. 高频踩坑与排查技巧实录4.1 visited 数组没有重置多组测试反复出错这类问题的典型场景是在在线评测系统里跑多组测试数据第一组跑得好好的第二组开始遍历到的顶点明显变少。说句实话这绝对是我见过程序员掉进去次数最多的坑之一。原因很简单上一组测试跑完后visited 数组里留下了大量 true下一组测试开始时如果没有清空遍历函数看到这些 true 会以为顶点已经被访问过从而直接跳过。所以我在上面的 GraphMatrix 和 GraphAdj 类里每次 dfs/bfs 入口处都会调用 fill(visited.begin(), visited.end(), false)这个习惯能救很多次命。纯 C 项目里对应的做法是 memset(visited, 0, sizeof(visited))但如果你把 visited 作为指针传入函数sizeof(visited) 只能得到指针大小容易踩到一个经典错误应该写成 sizeof(int) * MAXV或者干脆在调用处 memset。最简单的建议把重置动作放在每次遍历之前做做成一个 resetVisited() 函数不要靠记忆到处补。4.2 递归 DFS 在大数据量下爆栈递归这枚硬币有反面。当图的顶点数达到几万甚至更多时递归深度可能非常深。如果整张图是一条链状结构DFS 每次只深入一个顶点那么递归深度就接近顶点数。C/C 的函数调用栈在主流系统上一般是几 MB 到十几 MB 的量级每层递归需要消耗栈帧深度达到数万层就可能触发段错误。这种问题在线评测系统里经常出现小数据样例全过大数据一提交就崩溃。解法是把递归改成显式栈。自己维护一个 stack 逻辑类似 BFS 但把队列换成栈void dfsIterative(int start) { fill(visited.begin(), visited.end(), false); stackint st; st.push(start); visited[start] true; while (!st.empty()) { int cur st.top(); st.pop(); cout cur ; // 逆序压栈保证弹出顺序和递归版本一致 for (int i n - 1; i 0; --i) { if (matrix[cur][i] !visited[i]) { visited[i] true; st.push(i); } } } }如果你用邻接表逆序压栈没有矩阵那么方便可以接受弹出顺序不同或者先遍历收集邻居再逆序 push。我的经验是做笔试和面试时如果面试官没有明确要求非递归优先用递归版因为思路清晰不容易写错但如果明确说“图规模很大必须迭代”那用显式栈版本更稳妥。4.3 邻接矩阵空间超出预期栈放不下在本地调试时我见过有人这样写int graph[10005][10005]; 放在 main 函数内部。你猜怎么着编译能过但一运行就崩溃。原因不是代码逻辑错而是这个数组大小约为 1 亿个 int400MB远超函数栈所能容纳的空间。解决办法有三个方向一是把数组声明为全局变量放到静态存储区二是用 vectorvector graph(n, vector (n, 0))数据分配在堆上三是用 C 语言手动 malloc 二维数组。我的建议是刷题阶段尽量用 vector省心自动管理内存。如果是纯 C 实验必须用全局数组或 malloc不要试图在函数体内塞一个巨大的定长二维数组。4.4 邻接表删除边和重边处理的“扰人问题”邻接表在插入边时非常爽但删除边就要细心。vector 的删除需要遍历对应链表找到目标后 erase时间复杂度 O(degree)。如果代码里同时存在无向图双向添加、而且输入数据本身包含重边那么图中可能藏着两条完全一样的边。遍历和普通 DFS 不会受到太大影响但你要是统计每个顶点的度数或者做欧拉路径这类必须恰好用完每条边的算法重边就会导致结果错误。这种情况下我一般会根据题目要求决定要不要去重可以用 set 先做一层过滤也可以读入完成后对每个顶点的邻接表 sort unique再重建 vector。基础操作的代码可以不去重但心里要时刻有“重边可能是坑”这根弦。我把上述典型问题整理成了一张速查表方便以后自查现象可能原因解决思路第二组数据遍历结果变少visited 数组未重置每次遍历前调用 fill 或 memset大数据下程序段错误退出递归深度过大导致爆栈改为显式栈的迭代 DFS邻接矩阵程序启动即崩溃大数组放在函数栈中改用 vector 或全局数组BFS 输出出现重复顶点出队时才标记 visited改为入队立即标记图似乎“半连通”无向边只添加了一个方向addEdge 中双向添加统计数据与预期不符重边没有被过滤视题目要求用 set 或 sort unique 去重5. 实操心得与扩展方向5.1 给初学者的落地学习顺序我见过不少人被图的基本操作劝退往往是因为一上来就想把两种存储加上两种遍历一次性全部拿下结果代码越写越乱。我的建议是分四步走。第一步在纸上画出一个 5 到 7 个顶点的小图手动推演 DFS 和 BFS 的访问序列。第二步只写邻接矩阵版本把加边、DFS、BFS 全部跑通与手推序列对照。第三步加上连通分量计数、路径判断这些延伸操作。第四步换成邻接表版本体会两者的代码差异。等这四步都做熟再去看最短路径、最小生成树你会明显感觉顺畅很多。反过来如果连“从 0 出发能不能到 6”这类判断都要现翻代码那图论算法基本无从谈起。5.2 从基本操作能延伸出哪些算法图的基本操作是所有后续算法的地基。基于 BFS可以解决无权图最短路、层序遍历、多源扩散模型在 BFS/DFS 的基础上加上“选择最小权值边”的策略就是 Prim 或 Kruskal 最小生成树把 DFS 与“松弛”操作结合就走向了 Dijkstra在有向无环图上使用 DFS 拓扑排序又是课程安排、任务编排类问题的基础。实际工程项目里模块之间的依赖分析、持续集成流水线的调度等本质上都是把依赖关系建模成图再执行拓扑操作。基础夯实后你会发现“图”这个概念像乐高积木一样可以被拼成各种解决现实问题的算法模型。5.3 我最想提醒的一个习惯说了这么多实现细节最后想分享一个个人体会写图算法前先花 30 秒在图上面标注几个关键信息——是无向还是有向、边是否带权、是否允许重边和自环、顶点编号从 0 还是从 1 开始。我有太多次因为没注意顶点编号从 1 开始导致数组开小一个位置或者建图时漏了 -1 转换调试到怀疑人生。图的基本操作本身不难但它对细节的敏感度要求很高养成“先看清楚再动手”的习惯节省的时间远比想象中多。