1. 图与深度优先遍历从“走迷宫”说起大家好我是老陈在算法和数据结构这块摸爬滚打了十几年今天想和大家聊聊图的深度优先遍历。很多刚接触图论的朋友会觉得这东西很抽象一堆点和线算法绕来绕去。其实啊你可以把它想象成在一个巨大的迷宫里探险。想象一下你站在一个岔路口面前有好几条路。深度优先遍历的策略就是认准一条路走到黑。你选择最左边那条路一直往里走遇到新的岔路口继续选最左边的路深入直到走到死胡同。然后你退回上一个岔路口试试刚才没走的第二条路再继续深入……这种“不撞南墙不回头”的探索方式就是深度优先遍历的精髓。它非常适合用来解决“能不能走到终点”、“一共有多少条路径”这类需要彻底探索的问题。在计算机里“图”就是用来表示这种多对多关系的结构。比如微信里的好友关系你认识AA认识BB又认识C城市之间的交通网甚至是网页之间的超链接都可以用图来表示。我们今天要用的C来实现它就是因为C效率高控制力强能让我们清晰地看到算法每一步是怎么运作的。理解了它你就能自己动手分析社交网络、寻找最优路径甚至设计简单的游戏AI了。2. 图的存储如何为你的“迷宫”画地图在开始“探险”之前我们得先有一张清晰的迷宫地图。在程序里这就是图的存储。如果存储方式没选好后续遍历就会又慢又麻烦。原始文章提到了两种方式我这里展开讲讲并说说我们实际项目中更常用的方法。2.1 邻接矩阵简单粗暴的二维表格第一种最直观的想法是用一个二维数组矩阵来存。假设我们有5个城市编号0到4如果城市0和城市2之间有路我们就在矩阵的[0][2]和[2][0]位置标记为1否则为0。对于带权重的图比如距离这里就可以存具体的数值。// 假设最多有100个顶点 const int MAXN 100; int graph[MAXN][MAXN] {0}; // 添加一条从顶点a到顶点b的边无向图 void addEdge(int a, int b) { graph[a][b] 1; graph[b][a] 1; // 如果是无向图需要对称设置 }优点查询任意两个点之间是否有边速度极快O(1)时间搞定。实现也超级简单。缺点太浪费空间了如果图里有10000个点但只有20000条边这种边数远小于顶点数平方的图叫“稀疏图”这个10000x10000的矩阵里绝大部分都是0空间利用率极低。而且想找一个点的所有邻居你得把一整行都扫描一遍。所以邻接矩阵就像一份巨细无遗的全国地图连你家门口到邻居家的土路都印在上面虽然查起来快但携带和翻阅起来实在太笨重了。对于大多数实际问题我们用的是下面这种更灵活的方法。2.2 邻接表像通讯录一样的存储方式原始文章里用的vectorint node[MAXN]就是邻接表的一种实现。它的思想特别自然我为每个顶点都维护一个列表比如数组或链表这个列表里只存放和它直接相连的邻居顶点。这就好比你的手机通讯录。你顶点的通讯录列表里只存了你朋友的电话号码邻居顶点。你想知道和谁有联系翻自己的通讯录就行了不用去查全世界所有人的名单。在C里用vector数组来实现邻接表是最方便的选择之一#include vector using namespace std; const int MAXN 20010; // 预设最大顶点数 vectorint adjList[MAXN]; // 邻接表adjList[i]存储顶点i的所有邻居 int main() { int vertexCount, edgeCount; // 顶点数边数 cin vertexCount edgeCount; // 读入边构建图 for (int i 0; i edgeCount; i) { int a, b; cin a b; // 假设是无向图边是双向的 adjList[a].push_back(b); adjList[b].push_back(a); } // ... 后续遍历操作 }为什么用vector因为它动态管理内存用多少申请多少完美契合稀疏图的需求。查找一个顶点的所有邻居直接遍历它的vector就行非常高效。这也是原始文章采用的方法确实是在工程和竞赛中最常见、最实用的选择。这里有个细节原始文章在输入后对每个顶点的邻居列表进行了排序sort。这是一个非常好的习惯特别是题目要求按特定顺序比如编号从小到大遍历时。排序保证了我们每次访问邻居的顺序是一致的、可预期的这在很多场景下至关重要。3. 深度优先遍历的核心思想与递归实现地图准备好了现在正式进入迷宫探险环节——深度优先遍历。我们前面打了比方是“一条路走到黑”用专业点的说法这叫“尽可能深”的搜索策略。它的核心过程可以概括为三步访问当前顶点比如打印它的编号。标记当前顶点为已访问防止后面绕圈子重复访问。递归访问未访问过的邻居对每一个邻居重复步骤1-3。这个过程天然适合用递归来实现因为“探索下一个顶点”这个动作和“探索当前顶点”的动作是完全一样的。我们来看一个比原始文章更清晰一些的递归函数// 访问标记数组全局变量初始值默认为0false bool visited[MAXN] {false}; // 深度优先遍历的递归函数 void dfs(int currentVertex) { // 1. 访问当前顶点 cout currentVertex ; // 2. 标记为已访问 visited[currentVertex] true; // 3. 递归访问所有未访问的邻居 for (int neighbor : adjList[currentVertex]) { if (!visited[neighbor]) { dfs(neighbor); // 这里就是“深度”的体现立刻深入这个邻居 } } }我来说说这里面的几个关键点也是新手容易迷糊的地方。递归是怎么“一条路走到黑”的假设我们从顶点0开始它有两个邻居1和2。for循环先遇到邻居1发现visited[1]是false立刻调用dfs(1)。这时函数栈切换到dfs(1)的执行上下文它去处理顶点1打印1标记1。如果顶点1有邻居3它又会立刻调用dfs(3)……就这样一层套一层地递归下去直到某个顶点没有未访问的邻居了死胡同递归开始逐层返回。当dfs(1)的for循环执行完返回到dfs(0)时才会继续检查顶点0的下一个邻居2。所以顺序上是先彻底挖完0-1-3…这条分支再回头处理0-2这条分支。visited数组为什么这么重要图里可能有环比如A连BB连CC又连回A。如果没有visited标记算法会在A、B、C之间无限递归下去直到程序栈溢出崩溃。visited数组就是我们的“粉笔”在走过的路口画个记号告诉自己和后来者“此路已探不必再进”。原始文章中的dfs和dfs_1它把逻辑拆成了两个函数这其实是一种更工程化的写法。dfs(int nd)负责从nd顶点开始探索它能到达的整个连通区域。而dfs_1(int wi)则负责遍历所有顶点确保即使图不是完全连通的有多个孤立的子图每一个顶点都不会被漏掉。这种写法在处理非连通图时非常清晰。4. 非递归实现用栈来模拟递归过程递归写法虽然直观但有个潜在问题如果图非常非常深比如一条几万个个顶点的链递归调用层数过深可能导致栈溢出。别担心所有递归算法都可以用循环和栈来改写。深度优先遍历的非递归实现就是显式地使用一个栈来保存我们需要回溯的路径。我们来手动模拟一下这个过程这能帮你彻底理解DFS的机制把起始顶点压入栈并标记为已访问。只要栈不为空就循环 a. 取出栈顶顶点查看当前走到哪了。 b. 访问它如果需要。 c. 把这个顶点的所有未访问的邻居压入栈中。注意这里有个关键为了和递归顺序一致比如先访问编号小的我们压栈的顺序可能需要反向处理。void dfs_iterative(int startVertex) { bool visited[MAXN] {false}; stackint s; // 起始点入栈并标记 s.push(startVertex); visited[startVertex] true; // 注意标记在入栈时就要做防止重复入栈 while (!s.empty()) { int current s.top(); s.pop(); cout current ; // 访问栈顶元素 // 为了与递归先访问vector中靠前的邻居顺序一致 // 我们需要将邻居逆序压栈。这样栈顶才是下一个该访问的顶点。 // 例如邻居有[1,2,3]递归先访问1。我们压栈顺序应为3,2,1这样1在栈顶。 for (auto it adjList[current].rbegin(); it ! adjList[current].rend(); it) { int neighbor *it; if (!visited[neighbor]) { visited[neighbor] true; // 标记必须在入栈前完成 s.push(neighbor); } } } }非递归的优势完全避免了递归的函数调用开销和栈溢出风险对于深度极大的图更安全。需要注意的坑标记访问的时机一定要在顶点入栈时就标记为已访问。如果等到出栈时才标记同一个顶点可能会被其他路径重复压入栈中多次导致错误和性能下降。这是我早期踩过的一个典型坑。5. 实战应用DFS能解决哪些实际问题光会写算法模板不够咱得知道这玩意儿能干嘛。DFS的应用场景比你想象的要广得多我挑几个经典的说说。5.1 查找路径与连通性这是最直接的应用。给定起点和终点DFS能帮你找出一条可行的路径不一定是最短。判断两个点是否连通比如社交网络里两个人是否间接认识用DFS从一点出发看能否访问到另一点就行了。// 判断从start到target是否存在路径 bool hasPath(int start, int target) { bool visited[MAXN] {false}; return dfs_check(start, target, visited); } bool dfs_check(int current, int target, bool visited[]) { if (current target) return true; visited[current] true; for (int neighbor : adjList[current]) { if (!visited[neighbor]) { if (dfs_check(neighbor, target, visited)) { return true; // 找到路径立即层层返回true } } } return false; // 当前分支找不到 }5.2 拓扑排序这个在安排课程计划、编译任务依赖时特别有用。比如学《数据结构》前必须先学《C编程》这种先后关系构成一个有向无环图。DFS可以生成一个合法的学习顺序。基本思路是在DFS回溯的时候将顶点加入一个列表这个列表的逆序就是一个拓扑排序。5.3 检测环在任务调度里如果依赖关系形成了环A依赖BB依赖CC又依赖A那就死锁了永远无法执行。用DFS可以检测有向图中是否存在环。方法是在递归过程中除了visited数组再维护一个onStack数组记录当前递归栈上的顶点。如果在探索邻居时发现一个邻居已经在onStack上说明找到了一个环。5.4 寻找连通分量很多图不是完全连通的。比如一个社交网络可能由几个互不关联的小圈子组成。用原始文章中dfs_1那样的方式对每个未访问的顶点调用dfs每一次调用就探索出了一个完整的连通分量小圈子。统计调用了几次dfs就知道图里有几个独立的部分。6. 性能优化与避坑指南代码能跑起来只是第一步跑得好、跑得稳才是高手追求的目标。基于DFS有几个常见的优化点和坑需要注意。6.1 选择合适的存储结构前面已经详细讨论过对于稀疏图无脑用邻接表vectorint adjList[N]。在顶点数N很大10^5时用vector数组可能栈空间开销大可以考虑用vectorvectorint adjList动态创建或者用链表但vector通常性能更好。对于稠密图边数接近顶点数的平方或者需要频繁判断任意两点间是否有边才考虑邻接矩阵。6.2 输入规模与递归深度这是新手最容易栽跟头的地方。如果题目明确顶点数可能达到10^5级别并且图可能退化成一条长链那么递归DFS很可能导致栈溢出。解决办法有两个改用非递归栈实现如上文所述。在编译或运行时增大线程栈大小不推荐作为通用解法但在某些竞赛环境中是技巧。例如在GCC中可以用-Wl,--stack,16777216来设置更大的栈空间。6.3 剪枝的重要性DFS是一种暴力搜索如果不加约束它会遍历所有可能的路径复杂度是指数级的。剪枝就是在搜索过程中提前判断出某些分支不可能产生有效结果从而直接放弃对该分支的深入探索。比如在寻找路径时如果当前路径长度已经超过了已知的最短长度就没必要再往下走了。剪枝是优化DFS搜索效率最关键的艺术需要根据具体问题设计。6.4 复杂度分析对于邻接表存储的图DFS的时间复杂度是O(V E)其中V是顶点数E是边数。因为每个顶点和每条边都只会被访问一次。空间复杂度主要是递归调用栈或显式栈的开销最坏情况是O(V)。记住这个公式在分析问题复杂度时非常有用。7. 完整代码示例与逐行解析最后我们把所有知识点串起来写一个比原始文章更健壮、注释更完整的可运行示例。这个例子处理一个无向图并确保即使是非连通图也能完整遍历。#include iostream #include vector #include algorithm // 用于sort using namespace std; const int MAXN 1000; // 根据问题要求调整最大顶点数 // 全局邻接表和访问数组 vectorint adjList[MAXN]; bool visited[MAXN] {false}; /** * 深度优先遍历递归函数 * param current 当前正在访问的顶点 */ void dfs(int current) { // 访问当前顶点这里简单打印 cout current ; // 标记已访问 visited[current] true; // 遍历当前顶点的所有邻居 for (int i 0; i adjList[current].size(); i) { int nextVertex adjList[current][i]; // 如果邻居未被访问则深入探索 if (!visited[nextVertex]) { dfs(nextVertex); } } } /** * 对整个图进行DFS确保遍历所有连通分量 * param vertexCount 图中顶点的总数 */ void dfsTraversal(int vertexCount) { // 初始化访问标记 fill(visited, visited vertexCount, false); // 比循环赋值更C的方式 cout 深度优先遍历结果: ; for (int v 0; v vertexCount; v) { // 如果这个顶点还没被访问过说明它属于一个新的连通分量 if (!visited[v]) { dfs(v); // 如果需要区分不同连通分量可以在这里换行或加标记 // cout endl 新的连通分量: ; } } cout endl; } int main() { int vertexCount, edgeCount; cout 输入顶点数和边数: ; cin vertexCount edgeCount; cout 输入 edgeCount 条边 (格式: 起点 终点): endl; for (int i 0; i edgeCount; i) { int u, v; cin u v; // 构建无向图两边都要加 adjList[u].push_back(v); adjList[v].push_back(u); } // 可选对每个顶点的邻居列表进行排序保证遍历顺序一致如从小到大 cout 正在对邻接表排序... endl; for (int i 0; i vertexCount; i) { if (!adjList[i].empty()) { sort(adjList[i].begin(), adjList[i].end()); } } // 执行深度优先遍历 dfsTraversal(vertexCount); return 0; }运行流程解析程序首先读入顶点数和边数。循环读入每条边构建无向图的邻接表。注意u和v互相加入对方的列表。对每个顶点的邻居列表排序。这一步不是DFS必须的但能保证输出顺序固定便于调试和符合某些题目要求。dfsTraversal函数是入口。它首先重置visited数组然后遍历所有顶点。一旦发现未访问的顶点就调用dfs深入探索其所在的整个连通区域。dfs函数是核心递归。它打印当前顶点标记访问然后对其每一个未访问的邻居递归调用自身。你可以用下面这个简单的图来测试输入顶点数和边数: 6 5 输入5条边 (格式: 起点 终点): 0 1 0 2 1 3 2 4 4 5这是一个非连通图吗不它是连通的。遍历输出可能是0 1 3 2 4 5取决于排序和递归顺序。如果去掉0 2这条边图就变成了两个连通分量我们的代码依然能正确输出所有顶点。写到这里关于C中图的深度优先遍历从思想、存储、实现到优化和应用我已经把我觉得最重要的经验和细节都分享出来了。算法学习最怕的就是只看不练。我建议你最好能把上面的代码自己敲一遍用不同的图去测试尝试修改成有向图或者自己实现一下非递归版本。遇到问题就调试看看visited数组是怎么变化的栈是怎么压入弹出的。这个过程里踩的坑比你读十篇文章记得都牢。图论的世界很大DFS是一把打开许多大门的钥匙希望你能用好它。