企业官网建设流程全解析

开头

图这一章，我见过太多同学栽在同一个地方：代码看懂了，课堂例题也听明白了，可一到自己上手写，要么在存储结构上纠结半天，要么在遍历顺序上绕不出来。这篇是“1小时数据结构”系列的第二十五篇，专讲图最基础也最核心的两个遍历算法——BFS（广度优先遍历）和DFS（深度优先遍历），全篇使用C++描述。目标很明确：让你在一个小时内，从建图到两种遍历全部跑通，并且能说清楚它们各自适合解决什么问题。

这篇文章适合三类人：正在学数据结构、被图的遍历卡住的在校同学；准备面试、想快速捡起图论基础知识的求职者；以及工作中需要处理图数据、但平时不太写图算法的开发者。前面理解起来都不难，关键是把“为什么这么做”想明白，所以我不仅给代码，还会解释每个核心步骤背后的逻辑。准备好了就开始，读完你会觉得图其实没那么可怕。

1. 图的存储结构准备——遍历开始前，先解决“图怎么放进电脑”

学遍历之前，必须先解决一个问题：图在代码里长什么样？这是所有图算法的基础。你不可能绕过存储结构直接写遍历，就像你要遍历一棵树，总得先把树节点存下来。图的存储方式主流就两种：邻接矩阵和邻接表。搞清楚这两者的差异，你的遍历代码才有立足点。

1.1 邻接矩阵：最直观，但空间上是“大户”

邻接矩阵的思路很简单：开一个 N × N 的二维数组，matrix[i][j]表示顶点 i 到顶点 j 是否有边。有边记为 1（或权重），无边记为 0（或用一个大数表示无穷）。

// 邻接矩阵建图：N个顶点，M条边 #include <iostream> #include <vector> using namespace std; int main() { int N = 5, M = 6; vector<vector<int>> matrix(N, vector<int>(N, 0)); // 假设输入6条边，每条边两个端点 int edges[6][2] = {{0,1},{0,2},{1,2},{1,3},{2,4},{3,4}}; for (int i = 0; i < M; ++i) { int u = edges[i][0], v = edges[i][1]; matrix[u][v] = 1; matrix[v][u] = 1; // 无向图需要对称赋值 } // 遍历输出 for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cout << matrix[i][j] << " "; } cout << endl; } return 0; }

注意无向图的矩阵一定是沿着主对角线对称的。如果你在初始化或更新边的时候只写了matrix[u][v] = 1而忘了反向，那么后面遍历的时候，从 v 就永远访问不到 u，查 bug 会查得你很崩溃。这是我见过新手最常犯的错误之一。

邻接矩阵最大的好处是查询两点之间是否有边，时间复杂度是 O(1)，非常快。代价是空间总是 N²——即便你的图只有几条边，也得开一个完整的二维数组。N 稍微大一点，比如 5000 个顶点，开 5000×5000 的 int 数组就是 100MB 内存，这在很多题目环境里直接超限。

1.2 邻接表：稀疏图的主力，也是我推荐的首选

邻接表换了个思路：每个顶点只存储“和它相连的邻居”，用一个数组的数组（vector<vector<int>>）来表示。

#include <iostream> #include <vector> using namespace std; int main() { int N = 5, M = 6; vector<vector<int>> adj(N); // 每个顶点对应一个动态数组 int edges[6][2] = {{0,1},{0,2},{1,2},{1,3},{2,4},{3,4}}; for (int i = 0; i < M; ++i) { int u = edges[i][0], v = edges[i][1]; adj[u].push_back(v); adj[v].push_back(u); // 无向图对称添加 } // 打印邻接表 for (int i = 0; i < N; ++i) { cout << "顶点 " << i << ": "; for (int v : adj[i]) { cout << v << " "; } cout << endl; } return 0; }

邻接表的空间复杂度是 O(N + E)，E 是边数。对于稀疏图（边数远小于 N²），它比邻接矩阵省得多。而且在实际的图论题目里，绝大多数场景都是稀疏图，所以邻接表几乎成了默认选择。它的缺点是查询两点之间是否有边需要遍历邻居列表，最坏是 O(度数)，但这在遍历算法中并不是瓶颈。

1.3 选型心得：不要只会一种，要按场景换

我的建议很简单：做笔试、面试题的时候，无脑选邻接表，它能应付 95% 以上的场景。但邻接矩阵你也得会写，因为有些题给了稠密图（N 小、边多），比如 N ≤ 200 时，用矩阵写起来更直观，判重也不容易出错。更关键的是，很多教材和考卷上给的伪代码是基于邻接矩阵的，你只会矩阵就会显得思维僵硬。

从0开始还是从1开始，这也是一个要提前统一的点。顶点编号如果从 0 开始，数组开 N 个就够；如果从 1 开始，数组要开 N+1 个，多出来的下标 0 留空。建议做题前先看清楚题目约定，否则建图就建错了，后面遍历全白做。

2. DFS遍历——一条路走到黑，撞了南墙再回头

DFS，深度优先遍历。这个名字很形象：它从一个顶点出发，尽可能深入地去访问每一个分支，直到这条路径走到尽头，再退回来（回溯）继续找其他没走过的分支。整个过程就像走迷宫时拿一根绳子，遇到分岔就选一条路走到底，走不通就往回退，换一条路再试。

2.1 递归版DFS：代码最短，思路最直

DFS 用递归写是最好理解的。递归就是系统帮你维护了一个栈：每一次函数调用都会把当前状态压栈，函数返回时自动弹栈，完全贴合 DFS 的“回溯”语义。

#include <iostream> #include <vector> using namespace std; vector<bool> visited; // 全局标记数组 vector<vector<int>> adj; void dfs(int u) { visited[u] = true; // 标记当前顶点已访问 cout << u << " "; // 访问当前顶点（前序位置） // 遍历所有邻接点 for (int v : adj[u]) { if (!visited[v]) { dfs(v); // 递归访问未访问的邻居 } } // 递归返回后，这里就是"后序位置"，可以处理回溯逻辑 } int main() { int N = 5, M = 6; adj.resize(N); visited.assign(N, false); int edges[6][2] = {{0,1},{0,2},{1,2},{1,3},{2,4},{3,4}}; for (int i = 0; i < M; ++i) { int u = edges[i][0], v = edges[i][1]; adj[u].push_back(v); adj[v].push_back(u); } // 从顶点0开始遍历 dfs(0); return 0; }

核心就三步：标记当前点、输出当前点、逐个递归未访问的邻居。这里有一个特别容易忽略的点：标记 visited 的动作必须在递归调用之前完成。为什么？因为如果不提前标记，假设 0 和 1 之间有边，1 和 0 之间也有边，从 0 递归到 1 后，你会发现 1 的邻居里有 0，而 0 还没被标记，于是又递归回 0，0 又递归到 1……无限递归，直接爆栈。这个坑，几乎每个初学图的人都会踩一次。

2.2 非递归版DFS：系统栈换显式栈

递归虽然清晰，但有一个现实问题：当图的顶点数很大（比如十万级）时，递归深度过大会导致函数调用栈溢出。这时候就要自己用栈模拟递归过程。

#include <iostream> #include <vector> #include <stack> using namespace std; void dfs_stack(int start, const vector<vector<int>>& adj) { int n = adj.size(); vector<bool> visited(n, false); stack<int> st; st.push(start); visited[start] = true; // 入栈即标记 cout << start << " "; while (!st.empty()) { int u = st.top(); bool hasUnvisited = false; // 找一个未访问的邻居 for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; st.push(v); cout << v << " "; hasUnvisited = true; break; // 只深入一个分支 } } // 如果没有未访问的邻居，说明当前分支走到底了，回溯 if (!hasUnvisited) { st.pop(); } } }

这里要注意一个关键差异：入栈时标记，不能出栈时标记。如果你在出栈时才标记 visited，那么同一个顶点可能会被入栈多次，因为它在栈里等待的过程中，有可能被其他路径再次发现。非递归 DFS 的遍历顺序跟递归版本在“同一层邻接点的被访问顺序”上可能略有差异，这是正常的，因为两者对下一个分支的选择顺序不同。你写的遍历顺序只要合法（每次只往未访问深处走），就是正确的 DFS。

2.3 DFS的三大经典应用场景

DFS 不只是用来打印遍历顺序的，它背后藏着一大票实用算法。第一，连通块计数：对整个图做主循环，每次遇到一个未访问顶点就启动一次 DFS，启动次数就是连通块数量。这在处理“图中多少个岛屿”“网络中有多少独立区域”这类问题上是标准解法。

第二，环路检测：DFS 过程中给每个顶点标记三种状态——未访问、正在访问（在递归栈中）、已访问完毕。如果 DFS 时碰到了一个“正在访问”状态的邻居，说明找到了一条回边，也就意味着图里有环。这个方法在有向图中尤其常用，因为无向图有环的检测要稍微绕一下（避免把父节点当成环）。

第三，拓扑排序：对有向无环图按 DFS 后序遍历的顺序倒序排列，就是拓扑序。很多教材把拓扑排序单独拿出来讲，但底层就是 DFS 加一个结果收集数组。所以 DFS 学好了，拓扑排序就是白送的。

3. BFS遍历——水面的涟漪，一圈一圈往外推

BFS，广度优先遍历。它的思想跟 DFS 完全相反：从一个顶点出发，先访问完它所有的邻居，再去访问邻居的邻居。整个过程像往水里扔一颗石子，涟漪从中心一圈一圈往外扩散。BFS 天然用来求无权图的最短路径，这是它最重要的价值所在。

3.1 BFS的队列实现与核心细节

BFS 离不开队列。为什么？因为你需要“排队等待”的机制：先访问离起点近的顶点，把它们塞进队列，稍后再处理它们引出的更远的邻居。

#include <iostream> #include <vector> #include <queue> using namespace std; void bfs(int start, const vector<vector<int>>& adj) { int n = adj.size(); vector<bool> visited(n, false); queue<int> q; q.push(start); visited[start] = true; cout << start << " "; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push(v); cout << v << " "; } } } }

BFS 的代码看起来跟非递归 DFS 很像，但有一个原则性的区别：入队时就要标记 visited，而不是出队时标记。我重点强调这一点，因为不这么做会导致同一个节点被多次入队。举个例子：起点 0 的邻居是 1 和 2，出队 0 之前你不标记 1、2，而是把它们入队并等到出队时才标记——假设 1 和 2 之间还有边，那么后来出队 1 时，发现 2 还在队列里且未被标记，又会把 2 再入队一次。队列里出现大量重复节点，遍历顺序被彻底打乱。这是 BFS 最常见的 bug，没有之一。

3.2 BFS与最短路径：从“有没有”到“怎么走”

BFS 最有价值的延伸，是求无权图（所有边权为 1）的单元最短路径。原理其实很朴素：BFS 逐层扩展，第一次访问到一个顶点时，走的路径一定是最短的，因为前面所有更短的路径都已经在这个点被访问之前尝试过了。

要输出具体路径，只需要额外维护一个 parent 数组：

#include <iostream> #include <vector> #include <queue> using namespace std; vector<int> bfs_shortest_path(int start, int target, const vector<vector<int>>& adj) { int n = adj.size(); vector<bool> visited(n, false); vector<int> parent(n, -1); // 记录每个顶点的前驱节点 queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); if (u == target) break; // 找到目标就提前结束 for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; parent[v] = u; // 关键：记录谁先发现了v q.push(v); } } } // 从target回溯到start，得到路径（注意是逆序） vector<int> path; for (int cur = target; cur != -1; cur = parent[cur]) { path.push_back(cur); } reverse(path.begin(), path.end()); return path; }

这里最关键的是parent[v] = u：当 u 第一次“发现”v 时，u 就是 v 在最短路径上的前驱。因为 BFS 的层次性，这个前驱关系天然保证了路径最短。最后从目标点一路往前回溯，就能还原出完整路径。注意我用了 reverse，因为从 target 回溯得到的是逆序。如果你忘了 reverse，输出的路径就是反的，这种错误不容易一眼看出来，需要调试时特别注意。这也是我在实际代码审查中经常给同学指出的问题——路径方向写反了，纯靠肉眼很难发现问题。

3.3 BFS在真实场景里的典型使用场景

BFS 的“层序扩散”特性，让它天然适合下面几类问题。第一，无权图最短路径，前面已经提过，这在迷宫寻路、A点到B点的最少步数问题上直接套用。第二，二分图判定：从一个顶点开始 BFS，给不同层的顶点交替染色，如果出现相邻顶点同色，说明不是二分图。这也是 BFS 一个非常经典且不限于遍历顺序的应用。

第三，社交网络中的“几度人脉”。你在某社交平台上看到“共同好友”“二度好友推荐”，背后的算法通常就是限定层数的 BFS：从你出发扩散一层得到好友，两层得到好友的好友。第四，单词阶梯游戏：给定一个起始单词和一个目标单词，每次只能改一个字母，求最短转换次数——把每个单词看作顶点，能相互转换的单词之间连边，BFS 跑一次就出来了。每次讲到这里，我都会让入门同学写一遍这个题目，因为完成它的过程，BFS 的“层”概念会被锤得很扎实。

4. DFS与BFS的横向对比——谁快谁慢，得看你想干什么

很多初学者的困惑是：既然两个都能遍历图，那到底该用哪个？答案是：都能遍历，但它们的“个性”完全不同。理解这种差异，比背下任何一行代码都重要。

4.1 复杂度视角：从大O角度看效率

先说大家最喜欢问的复杂度。无论是 DFS 还是 BFS，只要基于邻接表实现，时间复杂度都是 O(N + E)。N 是顶点数，E 是边数。为什么？因为遍历过程中，每个顶点都会被访问一次，而每条边也都会被“探查”一次（从一个端点看向另一个端点，判断对方是否被访问过）。所以遍历本身的时间开销是线性的，跟图的规模成正比。

如果用邻接矩阵实现，时间会变成 O(N²)。因为检查一个顶点的所有邻居需要扫一整行数组，N 个顶点就是 N×N。空间方面，DFS 的递归栈深度最坏是 N（图是一条链的时候），BFS 的队列长度在最坏情况下也是 N（一个顶点连接所有其他顶点的时候）。所以在大 O 意义上的空间复杂度，两者其实是同级的，并没有谁显著更省内存。

4.2 思路差异与选型原则：什么时候该用哪个

选型的第一条铁律：如果问题是“从起点到目标的最短路径”，优先考虑 BFS。原因是 BFS 的层次特性保证了第一次遇到目标节点时，路径一定是最短的。DFS 则做不到这一点——DFS 找到的一条路径只是“一条能到的路”，并不保证是最短的，要硬用 DFS 求最短路径，通常得配合回溯枚举所有路径，代价呈指数级。

第二条铁律：如果问题是“这个图是否连通”“一共有几个连通块”“是否存在某条路径”，DFS 往往写起来更简单。因为 DFS 的递归结构天生适合判断、回溯、计数这类需要“深挖到底”的操作。比如解数独、走迷宫是否可能到达终点，DFS 的逻辑更贴合人的直觉。

第三条没有谁绝对优秀：判断二分图、拓扑排序这类问题，BFS 和 DFS 都能做，选哪个取决于你更熟悉哪种写法。我个人习惯是二分图用 BFS，拓扑排序用 DFS，因为顺序不同、理解路径不同，各有所长。别逼着自己“只用一种遍历解决所有图问题”，算法是工具，灵活切换才是真功夫。

4.3 一道经典题目串起两个遍历

为了让你真正分清两者的差别，可以做一个典型例子：判断一个无向图共有几个连通块。我建议你先自己想用 DFS 和 BFS 各写一遍，然后把答案和下面的实现比对。这份代码我刻意保持很短，目的就是让你看出两种遍历在结构上的差别。

#include <iostream> #include <vector> #include <queue> using namespace std; void dfs_count(int u, vector<vector<int>>& adj, vector<bool>& visited) { visited[u] = true; for (int v : adj[u]) if (!visited[v]) dfs_count(v, adj, visited); } void bfs_count(int start, vector<vector<int>>& adj, vector<bool>& visited) { queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } } } int count_connected_components(vector<vector<int>>& adj) { int n = adj.size(); vector<bool> visited(n, false); int cnt = 0; for (int i = 0; i < n; ++i) { if (!visited[i]) { ++cnt; dfs_count(i, adj, visited); // 换成bfs_count同样可行 } } return cnt; }

看这段代码，你会发现外层循环完全一样，区别只在于“怎么从当前点扩展到整个连通块”。DFS 用递归一路挖到底，BFS 用队列一层层扩展，最终效果一致。所以从宏观上看，两种遍历只是“探索策略不同”，而不是“能力不同”。

5. 1小时实战路线图与避坑清单

标题里说“1小时数据结构”，那么这 1 小时到底怎么分配才能达到最好的学习效果？我给出一个可执行的方案，并且把新手最容易踩的坑替你提前排掉。

5.1 时间怎么分配：15分钟建图，30分钟遍历，15分钟写题

第一个 15 分钟，别写遍历，专门练建图。打开编辑器，把上面的邻接表和邻接矩阵各敲一遍，再把 N=8、M=10 的随机数据跑通。这一步的意义在于：建图代码是遍历的地基，地基不稳，后面你排查问题时会浪费更多时间。

第二个 30 分钟，先写 DFS 递归版和 BFS 队列版，吃透两段代码的运行过程。建议准备一支笔一张纸，画一个 6 个节点的图，手动按代码的逻辑模拟一遍访问顺序，你会突然发现遍历的每一步都有了画面感。然后再写非递归 DFS 和 BFS 最短路变体。

最后一个 15 分钟，把连通块计数和最短路径两个小题目各写一遍。不用贪多，写两道就够。这两个题目能把两种遍历的核心价值都体现出来，做完之后你基本就能在真实场景中选对算法。

5.2 高频问题速查表：新手必踩的五个坑

这里有个很典型的误解：有同学以为 visited 数组是优化选项，其实它不是。visited 是正确性保障，没有它 DFS 在无向图里必然死循环（因为两个相邻节点会互相发现对方）。你可以在一个只有两个节点的图上试一下：不标记 visited，DFS 会无限来回跳。

5.3 实战调试技巧：用一个“最小可复现案例”解决所有问题

排查遍历 bug 时，我从来不在大图上调试，而是固定用一张只有 5 个节点的图：

0 — 1 — 3 | | 2 4

这个图的好处很明显：节点少到肉眼能跟踪每一步；同时它既有“分叉”又有“环”，覆盖了大部分风险场景。调试时，在遍历函数里加几行日志，打印当前访问节点和标记节点的时机，然后手动模拟一遍，把预期输出和实际输出对比，很快就能定位问题出在哪里。

还有一个小技巧：写完遍历代码后，先用有向图跑一遍，再用无向图跑一遍。因为两种图的遍历在 visited 标记上的表现差异很明显，有向图跑通不代表无向图一定跑得通，反向边的存在会暴露出更多的“重复访问”问题。很多人只测无向图，导致在有向图场景下漏掉 bug。

结尾

最后分享一点我个人的习惯。在带新人学图遍历时，我从不让他们一上来就背模板，而是先在纸上把“从某个点出发，下一个访问谁、为什么是它”手推一遍。这个过程只要做过两三次，你就会发现 DFS 和 BFS 不再是一个需要记忆的代码片段，而是一种思维方式：遇到问题时，你会自然地判断“这个问题需要深挖下去找答案，还是逐层扩散找最近”。这种判断力才是图遍历真正给你的收获。下一次我们聊最小生成树的时候，你会发现 Kruskal 和 Prim 的核心基础，其实还是今天这两个遍历的思路。到时候你就知道，花这一个小时把 DFS、BFS 吃透，是绝对不亏的。