图的存储与遍历是所有算法工程师和一线开发都绕不开的基础话题。做推荐系统、社交网络分析、地图导航路径规划甚至游戏服务器里的 NPC 寻路只要和数据关系打交道就一定会撞上“图怎么存”和“图怎么走”这两个问题。这篇文章想从最常用的三种存储方案聊起再带你手写一遍 DFS 和 BFS最后分享几个在真实环境里特别容易踩的坑。适合正在补数据结构基础的读者也适合准备算法面试、想快速把图算法落地到业务里的朋友。1. 图的存储方案选型别让存储结构拖累算法性能1.1 邻接矩阵简单直观但注意空间天花板一个无向图有 V 个顶点、E 条边。邻接矩阵用二维数组g[V][V]表示顶点之间的关系g[u][v]为 1 表示 u 到 v 有边0 表示没有边。带权图可以把 1 换成权值没有边的地方用一个足够大的INF占位。这个方案为什么叫“简单直观”因为代码量非常少。建图的时候只需要“读一条边写两个位置”const int INF 0x3f3f3f3f; int g[MAXN][MAXN]; void addEdge(int u, int v, int w) { g[u][v] w; g[v][u] w; // 无向图 }空间复杂度是 O(V²)这个上限定得比较死。当 V 到 10000 时光是 bool 数组就要约 100MB如果存 int 权重10000²×4 字节约 400MB。所以邻接矩阵只适合顶点规模可控、边比较密的场景。一个很容易被忽视的问题是“遍历邻居”的效率。用邻接矩阵做 DFS 时每次访问某个顶点要扫描整行才能知道它到底连了哪些点。假设一个图有 1000 个顶点但只有 2000 条边它其实非常稀疏用邻接矩阵遍历时却要扫 1000×1000 个位置大量无效判断都在“这里没有边”上浪费了。从实际经验来看我会在顶点数不超过 2000、边很密集、需要频繁判断“u 和 v 之间是否存在边”的时候使用它。图论入门课也喜欢用邻接矩阵做示例因为它把边的存在性表达得极其直白。1.2 邻接表面向稀疏图的默认选项邻接表的思路是为每个顶点挂一条“邻居链”。每个顶点 u 用一个列表记录所有和它直接相连的顶点整体空间 O(VE)。C 里最舒服的写法是vector数组vectorint adj[MAXN]; // 带权图可以改成 vectorpairint,int void addEdge(int u, int v, int w) { adj[u].push_back(v); adj[v].push_back(u); }为什么它更适合稀疏图因为空间和边数成正比。同样是 1000 顶点、2000 条边邻接表只需要记录 2000 对关系遍历某个顶点时也只会访问真正的邻居不会做无意义的空扫描。这个优势在顶点数量大到万级甚至十万级时特别明显也是绝大多数生产级图算法实现的默认选择。邻接表里有个容易忽略的细节加边不是无成本的。vector动态扩容会拷贝已有元素如果边量很大建议先reserve预留容量或者直接用数组加头插法也就是下面要讲的链式前向星。另外删除边在邻接表里比较麻烦要遍历邻居列表。如果业务场景频繁删边不如考虑用哈希表或者平衡树存邻居集合但这是另一个复杂度层面的话题了。1.3 链式前向星竞赛与高性能场景的“隐藏利器”链式前向星可能很多人只在准备算法竞赛时见过但它其实是一个非常实用的数组结构。核心是用几个数组模拟邻接链表head[numVertex]存每个顶点第一条边的下标edge[to目标顶点, next同顶点下一条边下标, w权值]。遍历一个顶点的全部邻居时从head[u]出发一路沿着next指针走。struct Edge { int to, next, w; }; Edge edges[MAXM]; int head[MAXN], ecnt; void addEdge(int u, int v, int w) { edges[ecnt] {v, head[u], w}; head[u] ecnt; } // 无向图请记得加反向边注意头插法的效果是“后加的边反而先被遍历到”。如果你对遍历顺序有要求或者想保持输入顺序就必须意识到这一点。我见过不少新人在这个点上吃了亏以为输出顺序和输入顺序一致结果发现完全反了。链式前向星的空间利用率比vector邻接表更高因为vector的容量可能比实际元素大扩容时会预留多余空间而数组模拟链表是精确分配的。当边的数量级到百万、亿级时这个差距会直接影响内存够不够。它还能统一处理带权边、重边和反向边在最大流、最短路、网络流等算法里几乎是标配。三种存法我平时是这样选型的存储方式空间复杂度判断 uv 是否直接相连遍历 u 的所有邻居实现难度适合场景邻接矩阵O(V²)O(1)O(V)低稠密图、小图邻接表O(VE)扫描邻接表 O(degree(u))O(degree(u))低稀疏图、日常业务链式前向星O(VE)扫描邻接链表 O(degree(u))O(degree(u))中超大图、竞赛、网络流如果图特别小、又频繁判断“u 到 v 是否有边”邻接矩阵是最合适的如果平时做业务图分析、关系推荐邻接表最好写如果后面还要跑最短路、拓扑排序或者数据规模大到不想浪费额外内存链式前向星值得花一小时熟悉。我自己的习惯是除非题目限制严格否则日常开发和项目里优先用邻接表可读性和调试友好度最好。注意不要在稀疏大图上用邻接矩阵“图省事”。一旦顶点数量到几千内存和遍历开销会立刻让你后悔这个选择。2. 遍历算法的核心逻辑为什么 DFS 和 BFS 是万变不离其宗的基础2.1 深度优先遍历递归思想与回溯的真实面貌深度优先遍历简称 DFS思路用一句话概括从一个顶点出发能走多远就走多远走不动了再回头。它是递归思想最典型的应用场景之一。递归调用的本质是系统栈所以 DFS 天然借助函数调用时的栈帧记录“当前路径”。每次进入新顶点 u就把 u 标记为已访问然后依次尝试 u 的所有邻居如果某个邻居还没有被访问就递归进入那个邻居。代码框架非常简单bool visited[MAXN]; void dfs(int u) { visited[u] true; cout u ; for (int v : adj[u]) { if (!visited[v]) { dfs(v); } } }这里有个关键点visited必须在进入dfs的一开始置为 true而不是等递归返回后再置位。否则同一个节点可能被压进递归栈多次在大图里会直接导致栈溢出或指数级重复调用。理解遍历顺序的时候可以把图想象成迷宫你右手贴着墙壁一直走遇岔路先走最右边那条走到死胡同再原路退回到上一个岔路口继续试下一条路。这个“原路退回”的动作就是递归返回也是回溯思想的雏形。有向图和无向图在 DFS 上的区别在于可走方向不同。无向图里边的双向性让visited命中率更高有向图则可能出现大量“能到达却不回头”的路径分支画递归树的时候要多留心方向箭头的限制。如果不想用递归可以改用显式栈维护待访问顶点。但要注意显式栈的压栈顺序和递归顺序并不完全一致递归是“进入一个邻居后立刻处理这个邻居”显式栈如果一次把所有邻居压进去下一次弹出的往往是最后压入的那个所以遍历顺序会变成“后进先出”。很多人在这里调试半天才发现输出序列和递归版不一致其实只是栈的特性导致的自然差异不是写错了。DFS 的复杂度是 O(VE)每个顶点只会被正式访问一次每条边在无向图中会被检查两次在有向图中会被检查一次。空间上递归栈最大深度和图的路径长度有关极端情况下会接近 V这也是在大图上必须警惕栈溢出的原因。2.2 广度优先遍历队列带来的“层序”效果广度优先遍历简称 BFS和 DFS 相反先把“一步能到的邻居”全部访问完再去看“两步能到的邻居”。它依赖队列严格遵循先进先出的顺序。每次从队首取出 u然后把它所有未访问的邻居入队并标记。#include queue void bfs(int start) { queueint q; q.push(start); visited[start] true; while (!q.empty()) { int u q.front(); q.pop(); cout u ; for (int v : adj[u]) { if (!visited[v]) { visited[v] true; q.push(v); } } } }队列天然带来了“按层扩展”的效果起点是第一层直接连接的邻居是第二层第二层顶点的邻居是第三层……所以 BFS 经常用来求无权图的最短路径因为第一次访问到某个顶点时走的步数一定是从起点到该顶点的最少边数。做二叉树的层序遍历时会发现它和图的 BFS 在结构上几乎同源。树本来就是一种特殊的图树的层序遍历就是用队列实现的 BFS只不过树的每个节点只有一个父节点不会重复出现。图的 BFS 额外要做的事情就是去重不然同一个顶点会通过多条路径反复入队队列可能被撑爆。BFS 的复杂度同样是 O(VE)。空间上队列里最多可能同时存“当前层 下一层”的大量顶点在分支特别大的图里峰值不一定低但通常会比邻接矩阵的存储开销小。如果你在写“多源 BFS”也就是把多个初始节点同时放进队列这套逻辑同样成立只是起点的先后顺序会影响访问顺序。2.3 遍历顺序背后的细节起点选择、连通性与孤立点很多初学者跑完一次 DFS 或 BFS发现只访问了一部分点就以为自己代码写错了。其实图不一定是连通的。无向图可能有多个连通分量有向图还分强连通分量单个起点只能覆盖它所在的那一块区域。所以处理整张图时标准姿势是遍历所有顶点for (int i 0; i n; i) { if (!visited[i]) { dfs(i); // 或者 bfs(i) } }这个外层循环的作用就是扫描所有连通分量让孤立点也能被照顾到。求图的连通分量数量、判断图是否连通本质上都是在外层循环里统计调用了多少次搜索。另一个细节是遍历序列会受到邻接点存储顺序的影响。邻接表每次都 push_back 到 vector 尾部DFS 会按边的输入顺序访问邻居链式前向星用头插法则会先把最后输入的邻居访问掉。这个差异不影响正确性但会影响输出序列进而影响某些依赖遍历顺序的算法行为。比如计算拓扑序时顺序不同最终拓扑结果也可能不同这时候需要根据题目要求选择头插还是尾插。有向图尤其需要留神如果用正向邻接表存边DFS 沿出边走如果某些场景需要逆向推导比如求所有能到达某个终点的节点就得额外维护一张反向邻接表。这不是存储结构的问题而是对边方向的定义要提前想清楚。3. 实操一次性写好可复用的图存储与遍历模板3.1 准备工作与数据约定动手写代码之前我建议先把三个问题定死不然中途改代码会非常痛苦。第一顶点编号从 0 还是 1 开始。竞赛题常见习惯是 1 到 N很多数据结构库习惯 0 到 N-1。我自己的代码里统一用 0 到 n-1除非题目明确要求从 1 开始。用邻接矩阵时编号还会影响数组下标提前定好能避免一整个 class 的 off-by-one 错误。第二无向边是否要存成两条有向边。几乎所有的无向图都可以转换成“双向有向边”处理存储上就是addEdge(u,v)和addEdge(v,u)各调一次。如果不这么做DFS/BFS 只能沿一个方向走遍历会漏点。第三数组大小提前规划。一般我会定义const int MAXN 100005和const int MAXM 200005。邻接表用 vector 动态分配内存问题不大链式前向星的edges数组必须精确按边数开无向图要开 2 倍边数否则很容易越界写坏内存。3.2 完整代码邻接表 DFS BFS 模板下面是一份我平时改一改就能用的 C 模板支持无向图和带权边遍历输出节点编号。#include bits/stdc.h using namespace std; const int MAXN 100005; vectorpairint, int adj[MAXN]; // (to, weight) void addEdge(int u, int v, int w 1) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); // 无向图加反向边 } void dfs(int u, vectorbool visited) { visited[u] true; cout u ; for (auto [v, w] : adj[u]) { if (!visited[v]) { dfs(v, visited); } } } void bfs(int start, vectorbool visited) { queueint q; q.push(start); visited[start] true; while (!q.empty()) { int u q.front(); q.pop(); cout u ; for (auto [v, w] : adj[u]) { if (!visited[v]) { visited[v] true; q.push(v); } } } } int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; addEdge(u, v, w); } vectorbool visited(n, false); cout DFS: ; for (int i 0; i n; i) { if (!visited[i]) dfs(i, visited); } cout \n; fill(visited.begin(), visited.end(), false); cout BFS: ; for (int i 0; i n; i) { if (!visited[i]) bfs(i, visited); } cout \n; return 0; }这份代码的特点是比较皮实。vectorpairint,int存带权邻居DFS 和 BFS 只依赖visited外层 for 循环保证了不连通图也能全量遍历。如果不想用 pair也可以拆成两个vector一个存to一个存w可读性看个人习惯就行。边数特别大的场景可以把vector换成链式前向星。核心操作就是保证头插法逻辑正确遍历邻居时从head[u]开始沿着next一直走到 -1 结束。性能更好但代码确实会比 vector 版长一些。3.3 进阶在遍历中解决实际问题只会打印遍历序列还不够图遍历的真正价值是给各种算法当地基。第一种需求是统计连通分量。直接复用外层 for 循环每调用一次搜索就加一int components 0; for (int i 0; i n; i) { if (!visited[i]) { components; bfs(i, visited); // 或者 dfs(i, visited) } }第二种需求是判断图是否有环。无向图判环可以在 DFS 里加一个参数parent访问邻居时如果发现邻居已被访问且不是自己的父节点说明存在环有向图判环则需要给每个节点标记三种状态未访问、在递归栈中、已完成。只要发现一个点在当前递归栈路径上再次出现就说明有向图存在环。两种写法差别很大面试时值得单独练习。第三种需求是求无权图最短路径。BFS 天然擅长这个只要把visited改成dist数组入队时同步记录距离vectorint dist(n, -1); queueint q; dist[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } }这里 -1 表示未访问dist值本身承担了去重和计数双重职责是 BFS 最常用的变体。如果想输出具体路径还得再存一个pre[v] u最后从终点倒着回溯到起点再反转序列。4. 常见问题与排查技巧实录4.1 递归栈溢出的处理深度优先的递归写法在顶点很多或图的路径很长时很容易触发栈溢出。印象最深的一次是本地数据规模到 10 万节点的链状图我直接递归 DFS程序跑着跑着就崩了。当时第一反应是检查数组越界后来才意识到是递归深度过大。解决方案无非两种。第一把递归改成显式栈自己维护stackint本质是用堆内存模拟函数调用栈。第二在支持调整栈大小的环境里调大递归栈但这不一定可行尤其在嵌入式环境或在线评测系统里最好还是从代码层面解决。我的习惯是小规模图用递归代码可读性好大规模图提前切到显式栈或者直接用 BFS。不要等线上崩了再挣扎写的时候就估算一下最大递归深度比较稳妥。4.2 visited 标记的位置入队时标记还是出队时标记BFS 里有一个很经典但也比较隐蔽的错误有人会在出队时才把visited置为 true。从单起点角度看依然能跑完但效率非常差因为同一个顶点可能会被多个邻居反复入队。举个极端例子高度连通的图里某个顶点有 50 个邻居如果在出队时才标记这个顶点可能被 50 个邻居各入队一次队列立刻膨胀处理次数从 O(VE) 退化成接近 O(VE) 的重复劳动。正确做法是入队时立刻标记。这样一旦某个顶点被某个邻居发现并放进了队列其他邻居再碰到它时就知道“已经有人在处理了”不会再重复入队。排查时可以打印每个顶点第一次入队和实际被访问的时机二者应当很接近如果不是多半就踩了这个坑。DFS 里同理。如果不在进入递归函数的那一刻设置visited而是等访问完再设置会在递归里形成大量重复路径严重时直接死循环。4.3 重边、自环、负权与孤立点图数据里还有一些“看着不合法但真实存在”的情况处理时各有讲究。重边指的是同一对顶点之间有多条边。邻接矩阵只会保留最后读到的一条邻接表和链式前向星会完整保存所有重边。对 DFS/BFS 来说重边几乎不影响正确性顶多多访问几次邻居但对最短路算法来说不同权值的重边会影响结果要结合需求决定是否去重。自环就是自己连自己。邻接矩阵里g[u][u] 1DFS 时访问到 u 自己因为visited[u]已经是 true所以会被跳过去。无向图的自环在链式前向星里同样只是多一次循环不会导致环路误判。真正需要注意的是“判断环”的 DFS 写法如果用“parentv 就跳过”的逻辑遇到自环要显式排除v u的情况。负权对纯粹存储和遍历没有影响因为遍历只关心是否访问过不关心边的权重。但一旦进入 Dijkstra 求最短路负权就会引发错误这时候要考虑 SPFA 或 Bellman-Ford 这类能处理负权的算法。孤立点则像“没有任何邻居”的节点。最容易漏掉的情况是只对起点做了一次 DFS结果发现孤立点没被访问。标准做法还是外层 for 循环从所有未访问的点分别出发。测试的时候我习惯故意放两个孤立点进去验证模板是否覆盖全面。4.4 调试小技巧打印邻接表与访问序列最后分享一个我自己一直在用的调试习惯。写完存储后先不要急着写遍历单独写一段“打印邻接表”的逻辑把每个顶点的邻居都打出来确认建图是否正确。这一步能筛掉至少一半的建图 bug比如无向图只加了一次边、权重赋值错误、边读入顺序异常等。遍历完以后打印访问序列再与手推顺序逐位对比。不要只看“大致差不多”要逐位对齐。如果多了一个点或少了一个点重点检查起点选择逻辑如果顺序混乱重点检查邻接表遍历方向、栈/队列使用方式以及visited标记时机。调试时把图缩到 5-6 个点、7-8 条边直接写进代码里跑。小数据里把逻辑走通后再替换成完整数据基本不会再有什么意外。我在第一次写链式前向星时也被head数组搞晕过一下午最后就是靠打印邻接表发现头插法和输入顺序不一致才彻底理解了整个结构。图算法不是“看会”的而是“调试会”的如果你正在学这部分内容拿到代码先跑小数据跑通后再自己尝试改一改比如把递归改成非递归、加距离数组、试试有向图判环。把这些变体都亲手写过一遍图的存储与遍历对你来说就不再是一堆概念而是真正的肌肉记忆了。
图存储与遍历：邻接矩阵、邻接表、链式前向星与DFS/BFS实践
图的存储与遍历是所有算法工程师和一线开发都绕不开的基础话题。做推荐系统、社交网络分析、地图导航路径规划甚至游戏服务器里的 NPC 寻路只要和数据关系打交道就一定会撞上“图怎么存”和“图怎么走”这两个问题。这篇文章想从最常用的三种存储方案聊起再带你手写一遍 DFS 和 BFS最后分享几个在真实环境里特别容易踩的坑。适合正在补数据结构基础的读者也适合准备算法面试、想快速把图算法落地到业务里的朋友。1. 图的存储方案选型别让存储结构拖累算法性能1.1 邻接矩阵简单直观但注意空间天花板一个无向图有 V 个顶点、E 条边。邻接矩阵用二维数组g[V][V]表示顶点之间的关系g[u][v]为 1 表示 u 到 v 有边0 表示没有边。带权图可以把 1 换成权值没有边的地方用一个足够大的INF占位。这个方案为什么叫“简单直观”因为代码量非常少。建图的时候只需要“读一条边写两个位置”const int INF 0x3f3f3f3f; int g[MAXN][MAXN]; void addEdge(int u, int v, int w) { g[u][v] w; g[v][u] w; // 无向图 }空间复杂度是 O(V²)这个上限定得比较死。当 V 到 10000 时光是 bool 数组就要约 100MB如果存 int 权重10000²×4 字节约 400MB。所以邻接矩阵只适合顶点规模可控、边比较密的场景。一个很容易被忽视的问题是“遍历邻居”的效率。用邻接矩阵做 DFS 时每次访问某个顶点要扫描整行才能知道它到底连了哪些点。假设一个图有 1000 个顶点但只有 2000 条边它其实非常稀疏用邻接矩阵遍历时却要扫 1000×1000 个位置大量无效判断都在“这里没有边”上浪费了。从实际经验来看我会在顶点数不超过 2000、边很密集、需要频繁判断“u 和 v 之间是否存在边”的时候使用它。图论入门课也喜欢用邻接矩阵做示例因为它把边的存在性表达得极其直白。1.2 邻接表面向稀疏图的默认选项邻接表的思路是为每个顶点挂一条“邻居链”。每个顶点 u 用一个列表记录所有和它直接相连的顶点整体空间 O(VE)。C 里最舒服的写法是vector数组vectorint adj[MAXN]; // 带权图可以改成 vectorpairint,int void addEdge(int u, int v, int w) { adj[u].push_back(v); adj[v].push_back(u); }为什么它更适合稀疏图因为空间和边数成正比。同样是 1000 顶点、2000 条边邻接表只需要记录 2000 对关系遍历某个顶点时也只会访问真正的邻居不会做无意义的空扫描。这个优势在顶点数量大到万级甚至十万级时特别明显也是绝大多数生产级图算法实现的默认选择。邻接表里有个容易忽略的细节加边不是无成本的。vector动态扩容会拷贝已有元素如果边量很大建议先reserve预留容量或者直接用数组加头插法也就是下面要讲的链式前向星。另外删除边在邻接表里比较麻烦要遍历邻居列表。如果业务场景频繁删边不如考虑用哈希表或者平衡树存邻居集合但这是另一个复杂度层面的话题了。1.3 链式前向星竞赛与高性能场景的“隐藏利器”链式前向星可能很多人只在准备算法竞赛时见过但它其实是一个非常实用的数组结构。核心是用几个数组模拟邻接链表head[numVertex]存每个顶点第一条边的下标edge[to目标顶点, next同顶点下一条边下标, w权值]。遍历一个顶点的全部邻居时从head[u]出发一路沿着next指针走。struct Edge { int to, next, w; }; Edge edges[MAXM]; int head[MAXN], ecnt; void addEdge(int u, int v, int w) { edges[ecnt] {v, head[u], w}; head[u] ecnt; } // 无向图请记得加反向边注意头插法的效果是“后加的边反而先被遍历到”。如果你对遍历顺序有要求或者想保持输入顺序就必须意识到这一点。我见过不少新人在这个点上吃了亏以为输出顺序和输入顺序一致结果发现完全反了。链式前向星的空间利用率比vector邻接表更高因为vector的容量可能比实际元素大扩容时会预留多余空间而数组模拟链表是精确分配的。当边的数量级到百万、亿级时这个差距会直接影响内存够不够。它还能统一处理带权边、重边和反向边在最大流、最短路、网络流等算法里几乎是标配。三种存法我平时是这样选型的存储方式空间复杂度判断 uv 是否直接相连遍历 u 的所有邻居实现难度适合场景邻接矩阵O(V²)O(1)O(V)低稠密图、小图邻接表O(VE)扫描邻接表 O(degree(u))O(degree(u))低稀疏图、日常业务链式前向星O(VE)扫描邻接链表 O(degree(u))O(degree(u))中超大图、竞赛、网络流如果图特别小、又频繁判断“u 到 v 是否有边”邻接矩阵是最合适的如果平时做业务图分析、关系推荐邻接表最好写如果后面还要跑最短路、拓扑排序或者数据规模大到不想浪费额外内存链式前向星值得花一小时熟悉。我自己的习惯是除非题目限制严格否则日常开发和项目里优先用邻接表可读性和调试友好度最好。注意不要在稀疏大图上用邻接矩阵“图省事”。一旦顶点数量到几千内存和遍历开销会立刻让你后悔这个选择。2. 遍历算法的核心逻辑为什么 DFS 和 BFS 是万变不离其宗的基础2.1 深度优先遍历递归思想与回溯的真实面貌深度优先遍历简称 DFS思路用一句话概括从一个顶点出发能走多远就走多远走不动了再回头。它是递归思想最典型的应用场景之一。递归调用的本质是系统栈所以 DFS 天然借助函数调用时的栈帧记录“当前路径”。每次进入新顶点 u就把 u 标记为已访问然后依次尝试 u 的所有邻居如果某个邻居还没有被访问就递归进入那个邻居。代码框架非常简单bool visited[MAXN]; void dfs(int u) { visited[u] true; cout u ; for (int v : adj[u]) { if (!visited[v]) { dfs(v); } } }这里有个关键点visited必须在进入dfs的一开始置为 true而不是等递归返回后再置位。否则同一个节点可能被压进递归栈多次在大图里会直接导致栈溢出或指数级重复调用。理解遍历顺序的时候可以把图想象成迷宫你右手贴着墙壁一直走遇岔路先走最右边那条走到死胡同再原路退回到上一个岔路口继续试下一条路。这个“原路退回”的动作就是递归返回也是回溯思想的雏形。有向图和无向图在 DFS 上的区别在于可走方向不同。无向图里边的双向性让visited命中率更高有向图则可能出现大量“能到达却不回头”的路径分支画递归树的时候要多留心方向箭头的限制。如果不想用递归可以改用显式栈维护待访问顶点。但要注意显式栈的压栈顺序和递归顺序并不完全一致递归是“进入一个邻居后立刻处理这个邻居”显式栈如果一次把所有邻居压进去下一次弹出的往往是最后压入的那个所以遍历顺序会变成“后进先出”。很多人在这里调试半天才发现输出序列和递归版不一致其实只是栈的特性导致的自然差异不是写错了。DFS 的复杂度是 O(VE)每个顶点只会被正式访问一次每条边在无向图中会被检查两次在有向图中会被检查一次。空间上递归栈最大深度和图的路径长度有关极端情况下会接近 V这也是在大图上必须警惕栈溢出的原因。2.2 广度优先遍历队列带来的“层序”效果广度优先遍历简称 BFS和 DFS 相反先把“一步能到的邻居”全部访问完再去看“两步能到的邻居”。它依赖队列严格遵循先进先出的顺序。每次从队首取出 u然后把它所有未访问的邻居入队并标记。#include queue void bfs(int start) { queueint q; q.push(start); visited[start] true; while (!q.empty()) { int u q.front(); q.pop(); cout u ; for (int v : adj[u]) { if (!visited[v]) { visited[v] true; q.push(v); } } } }队列天然带来了“按层扩展”的效果起点是第一层直接连接的邻居是第二层第二层顶点的邻居是第三层……所以 BFS 经常用来求无权图的最短路径因为第一次访问到某个顶点时走的步数一定是从起点到该顶点的最少边数。做二叉树的层序遍历时会发现它和图的 BFS 在结构上几乎同源。树本来就是一种特殊的图树的层序遍历就是用队列实现的 BFS只不过树的每个节点只有一个父节点不会重复出现。图的 BFS 额外要做的事情就是去重不然同一个顶点会通过多条路径反复入队队列可能被撑爆。BFS 的复杂度同样是 O(VE)。空间上队列里最多可能同时存“当前层 下一层”的大量顶点在分支特别大的图里峰值不一定低但通常会比邻接矩阵的存储开销小。如果你在写“多源 BFS”也就是把多个初始节点同时放进队列这套逻辑同样成立只是起点的先后顺序会影响访问顺序。2.3 遍历顺序背后的细节起点选择、连通性与孤立点很多初学者跑完一次 DFS 或 BFS发现只访问了一部分点就以为自己代码写错了。其实图不一定是连通的。无向图可能有多个连通分量有向图还分强连通分量单个起点只能覆盖它所在的那一块区域。所以处理整张图时标准姿势是遍历所有顶点for (int i 0; i n; i) { if (!visited[i]) { dfs(i); // 或者 bfs(i) } }这个外层循环的作用就是扫描所有连通分量让孤立点也能被照顾到。求图的连通分量数量、判断图是否连通本质上都是在外层循环里统计调用了多少次搜索。另一个细节是遍历序列会受到邻接点存储顺序的影响。邻接表每次都 push_back 到 vector 尾部DFS 会按边的输入顺序访问邻居链式前向星用头插法则会先把最后输入的邻居访问掉。这个差异不影响正确性但会影响输出序列进而影响某些依赖遍历顺序的算法行为。比如计算拓扑序时顺序不同最终拓扑结果也可能不同这时候需要根据题目要求选择头插还是尾插。有向图尤其需要留神如果用正向邻接表存边DFS 沿出边走如果某些场景需要逆向推导比如求所有能到达某个终点的节点就得额外维护一张反向邻接表。这不是存储结构的问题而是对边方向的定义要提前想清楚。3. 实操一次性写好可复用的图存储与遍历模板3.1 准备工作与数据约定动手写代码之前我建议先把三个问题定死不然中途改代码会非常痛苦。第一顶点编号从 0 还是 1 开始。竞赛题常见习惯是 1 到 N很多数据结构库习惯 0 到 N-1。我自己的代码里统一用 0 到 n-1除非题目明确要求从 1 开始。用邻接矩阵时编号还会影响数组下标提前定好能避免一整个 class 的 off-by-one 错误。第二无向边是否要存成两条有向边。几乎所有的无向图都可以转换成“双向有向边”处理存储上就是addEdge(u,v)和addEdge(v,u)各调一次。如果不这么做DFS/BFS 只能沿一个方向走遍历会漏点。第三数组大小提前规划。一般我会定义const int MAXN 100005和const int MAXM 200005。邻接表用 vector 动态分配内存问题不大链式前向星的edges数组必须精确按边数开无向图要开 2 倍边数否则很容易越界写坏内存。3.2 完整代码邻接表 DFS BFS 模板下面是一份我平时改一改就能用的 C 模板支持无向图和带权边遍历输出节点编号。#include bits/stdc.h using namespace std; const int MAXN 100005; vectorpairint, int adj[MAXN]; // (to, weight) void addEdge(int u, int v, int w 1) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); // 无向图加反向边 } void dfs(int u, vectorbool visited) { visited[u] true; cout u ; for (auto [v, w] : adj[u]) { if (!visited[v]) { dfs(v, visited); } } } void bfs(int start, vectorbool visited) { queueint q; q.push(start); visited[start] true; while (!q.empty()) { int u q.front(); q.pop(); cout u ; for (auto [v, w] : adj[u]) { if (!visited[v]) { visited[v] true; q.push(v); } } } } int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; addEdge(u, v, w); } vectorbool visited(n, false); cout DFS: ; for (int i 0; i n; i) { if (!visited[i]) dfs(i, visited); } cout \n; fill(visited.begin(), visited.end(), false); cout BFS: ; for (int i 0; i n; i) { if (!visited[i]) bfs(i, visited); } cout \n; return 0; }这份代码的特点是比较皮实。vectorpairint,int存带权邻居DFS 和 BFS 只依赖visited外层 for 循环保证了不连通图也能全量遍历。如果不想用 pair也可以拆成两个vector一个存to一个存w可读性看个人习惯就行。边数特别大的场景可以把vector换成链式前向星。核心操作就是保证头插法逻辑正确遍历邻居时从head[u]开始沿着next一直走到 -1 结束。性能更好但代码确实会比 vector 版长一些。3.3 进阶在遍历中解决实际问题只会打印遍历序列还不够图遍历的真正价值是给各种算法当地基。第一种需求是统计连通分量。直接复用外层 for 循环每调用一次搜索就加一int components 0; for (int i 0; i n; i) { if (!visited[i]) { components; bfs(i, visited); // 或者 dfs(i, visited) } }第二种需求是判断图是否有环。无向图判环可以在 DFS 里加一个参数parent访问邻居时如果发现邻居已被访问且不是自己的父节点说明存在环有向图判环则需要给每个节点标记三种状态未访问、在递归栈中、已完成。只要发现一个点在当前递归栈路径上再次出现就说明有向图存在环。两种写法差别很大面试时值得单独练习。第三种需求是求无权图最短路径。BFS 天然擅长这个只要把visited改成dist数组入队时同步记录距离vectorint dist(n, -1); queueint q; dist[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } }这里 -1 表示未访问dist值本身承担了去重和计数双重职责是 BFS 最常用的变体。如果想输出具体路径还得再存一个pre[v] u最后从终点倒着回溯到起点再反转序列。4. 常见问题与排查技巧实录4.1 递归栈溢出的处理深度优先的递归写法在顶点很多或图的路径很长时很容易触发栈溢出。印象最深的一次是本地数据规模到 10 万节点的链状图我直接递归 DFS程序跑着跑着就崩了。当时第一反应是检查数组越界后来才意识到是递归深度过大。解决方案无非两种。第一把递归改成显式栈自己维护stackint本质是用堆内存模拟函数调用栈。第二在支持调整栈大小的环境里调大递归栈但这不一定可行尤其在嵌入式环境或在线评测系统里最好还是从代码层面解决。我的习惯是小规模图用递归代码可读性好大规模图提前切到显式栈或者直接用 BFS。不要等线上崩了再挣扎写的时候就估算一下最大递归深度比较稳妥。4.2 visited 标记的位置入队时标记还是出队时标记BFS 里有一个很经典但也比较隐蔽的错误有人会在出队时才把visited置为 true。从单起点角度看依然能跑完但效率非常差因为同一个顶点可能会被多个邻居反复入队。举个极端例子高度连通的图里某个顶点有 50 个邻居如果在出队时才标记这个顶点可能被 50 个邻居各入队一次队列立刻膨胀处理次数从 O(VE) 退化成接近 O(VE) 的重复劳动。正确做法是入队时立刻标记。这样一旦某个顶点被某个邻居发现并放进了队列其他邻居再碰到它时就知道“已经有人在处理了”不会再重复入队。排查时可以打印每个顶点第一次入队和实际被访问的时机二者应当很接近如果不是多半就踩了这个坑。DFS 里同理。如果不在进入递归函数的那一刻设置visited而是等访问完再设置会在递归里形成大量重复路径严重时直接死循环。4.3 重边、自环、负权与孤立点图数据里还有一些“看着不合法但真实存在”的情况处理时各有讲究。重边指的是同一对顶点之间有多条边。邻接矩阵只会保留最后读到的一条邻接表和链式前向星会完整保存所有重边。对 DFS/BFS 来说重边几乎不影响正确性顶多多访问几次邻居但对最短路算法来说不同权值的重边会影响结果要结合需求决定是否去重。自环就是自己连自己。邻接矩阵里g[u][u] 1DFS 时访问到 u 自己因为visited[u]已经是 true所以会被跳过去。无向图的自环在链式前向星里同样只是多一次循环不会导致环路误判。真正需要注意的是“判断环”的 DFS 写法如果用“parentv 就跳过”的逻辑遇到自环要显式排除v u的情况。负权对纯粹存储和遍历没有影响因为遍历只关心是否访问过不关心边的权重。但一旦进入 Dijkstra 求最短路负权就会引发错误这时候要考虑 SPFA 或 Bellman-Ford 这类能处理负权的算法。孤立点则像“没有任何邻居”的节点。最容易漏掉的情况是只对起点做了一次 DFS结果发现孤立点没被访问。标准做法还是外层 for 循环从所有未访问的点分别出发。测试的时候我习惯故意放两个孤立点进去验证模板是否覆盖全面。4.4 调试小技巧打印邻接表与访问序列最后分享一个我自己一直在用的调试习惯。写完存储后先不要急着写遍历单独写一段“打印邻接表”的逻辑把每个顶点的邻居都打出来确认建图是否正确。这一步能筛掉至少一半的建图 bug比如无向图只加了一次边、权重赋值错误、边读入顺序异常等。遍历完以后打印访问序列再与手推顺序逐位对比。不要只看“大致差不多”要逐位对齐。如果多了一个点或少了一个点重点检查起点选择逻辑如果顺序混乱重点检查邻接表遍历方向、栈/队列使用方式以及visited标记时机。调试时把图缩到 5-6 个点、7-8 条边直接写进代码里跑。小数据里把逻辑走通后再替换成完整数据基本不会再有什么意外。我在第一次写链式前向星时也被head数组搞晕过一下午最后就是靠打印邻接表发现头插法和输入顺序不一致才彻底理解了整个结构。图算法不是“看会”的而是“调试会”的如果你正在学这部分内容拿到代码先跑小数据跑通后再自己尝试改一改比如把递归改成非递归、加距离数组、试试有向图判环。把这些变体都亲手写过一遍图的存储与遍历对你来说就不再是一堆概念而是真正的肌肉记忆了。