【算法精讲】深度优先搜索(DFS)，一文带你彻底掌握！✨

Ne0inhk

14 Mar 2026 — 12 min read

前言

亲爱的同学们，大家好！👋 今天我要和大家分享一个在算法世界中非常重要的搜索策略——深度优先搜索(Depth-First Search, DFS)。作为一名编程老师，我经常看到很多同学在面对图论和树的遍历问题时感到困惑，特别是当需要选择合适的搜索策略时。🤔

深度优先搜索就像是探险家在迷宫中的探索，总是沿着一条路径走到尽头，才会返回尝试其他路径。这种"一条路走到黑"的策略在解决许多实际问题中非常有效！今天，我们将一起深入了解DFS的原理、实现和应用，让你在算法的世界里多一把利器！💪

准备好开启这段探索之旅了吗？让我们一起出发吧！🚀

知识点说明

1. DFS的基本概念

深度优先搜索(DFS)是一种用于遍历或搜索树或图的算法。它的核心思想是：从起始节点开始，尽可能深入地探索一条路径，直到无法继续为止，然后回溯到前一个节点，继续探索其他未访问的路径。📝

DFS的三个关键特点：

优先深度：算法会尽可能深入地探索一条路径，而不是广泛地探索所有可能的路径
使用栈：DFS通常使用栈（或递归，隐式使用系统栈）来记住探索过程中的节点
回溯：当无法继续深入时，算法会回溯到前一个节点，尝试其他未探索的路径

2. DFS的基本步骤

实现DFS的基本步骤如下：

选择一个起始节点，将其标记为已访问，并放入栈中
当栈不为空时，执行以下操作：
- 取出栈顶节点作为当前节点
- 如果当前节点有未访问的相邻节点，选择一个，标记为已访问，并将其放入栈中
- 如果当前节点没有未访问的相邻节点，将其从栈中弹出（回溯）

重复步骤2，直到栈为空

3. DFS的两种实现方式

DFS有两种常见的实现方式：

递归实现

递归实现利用系统栈隐式地管理节点的访问顺序，代码简洁易懂：

publicvoiddfsRecursive(Graph graph,int vertex,boolean[] visited){// 标记当前节点为已访问 visited[vertex]=true;System.out.print(vertex +" ");// 递归访问所有未访问的邻接节点for(int neighbor : graph.getNeighbors(vertex)){if(!visited[neighbor]){dfsRecursive(graph, neighbor, visited);}}}

迭代实现

迭代实现使用显式的栈来管理节点的访问顺序：

publicvoiddfsIterative(Graph graph,int startVertex){boolean[] visited =newboolean[graph.getVertexCount()];Stack<Integer> stack =newStack<>();// 将起始节点标记为已访问并入栈 visited[startVertex]=true; stack.push(startVertex);System.out.print(startVertex +" ");while(!stack.isEmpty()){// 获取栈顶元素（但不移除）int currentVertex = stack.peek();// 查找未访问的邻接节点int nextVertex =findUnvisitedNeighbor(graph, currentVertex, visited);if(nextVertex !=-1){// 找到未访问的邻接节点，标记为已访问并入栈 visited[nextVertex]=true; stack.push(nextVertex);System.out.print(nextVertex +" ");}else{// 没有未访问的邻接节点，回溯（弹出栈顶元素） stack.pop();}}}privateintfindUnvisitedNeighbor(Graph graph,int vertex,boolean[] visited){List<Integer> neighbors = graph.getNeighbors(vertex);for(int neighbor : neighbors){if(!visited[neighbor]){return neighbor;}}return-1;// 没有未访问的邻接节点}

4. DFS的应用场景

DFS在实际编程中有广泛的应用：

路径查找：在迷宫或游戏中寻找从起点到终点的路径
拓扑排序：对有向无环图进行排序
连通性分析：确定图中的连通分量
环检测：检测图中是否存在环
二分图检测：判断一个图是否为二分图
强连通分量：查找有向图中的强连通分量（Kosaraju算法）

重难点说明

1. 理解回溯过程 🔄

DFS中最难理解的部分是回溯过程。当算法探索到一条路径的尽头时，需要回溯到前一个节点，继续探索其他路径。这个过程可以通过栈的操作来理解：

当我们访问一个节点时，将其压入栈中
当一个节点的所有邻接节点都被访问过后，将其从栈中弹出（回溯）
回溯后，我们回到了栈顶的节点，继续探索它的其他未访问邻接节点

想象你在探索一个迷宫，每当你走到一个分岔路口，你就在地图上标记当前位置。当你走到死胡同时，你需要回到上一个有未探索路径的分岔路口继续探索。这就是回溯的过程！🗺️

2. 避免环路导致的无限循环 ⚠️

在图中执行DFS时，如果存在环路且不正确处理已访问节点，可能会导致无限循环。因此，使用visited数组来标记已访问的节点是至关重要的。

例如，在一个简单的环A→B→C→A中，如果不标记已访问节点，算法会无限循环：A→B→C→A→B→C→…

3. 递归实现中的栈溢出问题 📚

递归实现DFS时，对于非常深的图或树，可能会导致栈溢出（StackOverflowError）。在这种情况下，应该考虑使用迭代实现。

迭代实现使用显式的栈，可以更好地控制内存使用，避免栈溢出问题。

4. 时间和空间复杂度分析 📊

时间复杂度：O(V + E)，其中V是节点数，E是边数。这是因为在最坏情况下，我们需要访问所有节点和边。
空间复杂度：O(V)，用于存储访问状态和递归调用栈（或显式栈）。

核心代码说明

让我们详细分析一下DFS的核心代码实现。以下是一个完整的Java实现示例，包含了递归和迭代两种方式：

importjava.util.*;// 图的邻接表表示classGraph{privateint vertexCount;privateList<List<Integer>> adjacencyList;publicGraph(int vertexCount){this.vertexCount = vertexCount; adjacencyList =newArrayList<>(vertexCount);for(int i =0; i < vertexCount; i++){ adjacencyList.add(newArrayList<>());}}publicvoidaddEdge(int source,int destination){ adjacencyList.get(source).add(destination);// 对于无向图，还需要添加反向边// adjacencyList.get(destination).add(source);}publicList<Integer>getNeighbors(int vertex){return adjacencyList.get(vertex);}publicintgetVertexCount(){return vertexCount;}}publicclassDFSExample{// 递归实现DFSpublicvoiddfsRecursive(Graph graph,int vertex,boolean[] visited){// 标记当前节点为已访问 visited[vertex]=true;System.out.print(vertex +" ");// 递归访问所有未访问的邻接节点for(int neighbor : graph.getNeighbors(vertex)){if(!visited[neighbor]){dfsRecursive(graph, neighbor, visited);}}}// 迭代实现DFSpublicvoiddfsIterative(Graph graph,int startVertex){boolean[] visited =newboolean[graph.getVertexCount()];Stack<Integer> stack =newStack<>();// 将起始节点标记为已访问并入栈 visited[startVertex]=true; stack.push(startVertex);System.out.print(startVertex +" ");while(!stack.isEmpty()){// 获取栈顶元素（但不移除）int currentVertex = stack.peek();// 查找未访问的邻接节点int nextVertex =findUnvisitedNeighbor(graph, currentVertex, visited);if(nextVertex !=-1){// 找到未访问的邻接节点，标记为已访问并入栈 visited[nextVertex]=true; stack.push(nextVertex);System.out.print(nextVertex +" ");}else{// 没有未访问的邻接节点，回溯（弹出栈顶元素） stack.pop();}}}privateintfindUnvisitedNeighbor(Graph graph,int vertex,boolean[] visited){List<Integer> neighbors = graph.getNeighbors(vertex);for(int neighbor : neighbors){if(!visited[neighbor]){return neighbor;}}return-1;// 没有未访问的邻接节点}// 主方法，用于测试publicstaticvoidmain(String[] args){// 创建一个有7个节点的图Graph graph =newGraph(7);// 添加边（对应示例中的图结构） graph.addEdge(0,1);// A -> B graph.addEdge(0,2);// A -> C graph.addEdge(1,3);// B -> D graph.addEdge(1,4);// B -> E graph.addEdge(2,5);// C -> F graph.addEdge(2,6);// C -> GDFSExample dfsExample =newDFSExample();System.out.println("递归DFS遍历结果：");boolean[] visited =newboolean[graph.getVertexCount()]; dfsExample.dfsRecursive(graph,0, visited);System.out.println("\n\n迭代DFS遍历结果："); dfsExample.dfsIterative(graph,0);}}

代码解析

Graph类：使用邻接表表示图，包含添加边和获取邻接节点的方法。
递归DFS：
- 标记当前节点为已访问
- 递归访问所有未访问的邻接节点
- 系统栈自动处理回溯过程
迭代DFS：
- 使用显式栈管理节点访问顺序
- 当栈不为空时，查找栈顶节点的未访问邻接节点
- 如果找到，将其标记为已访问并入栈
- 如果没有找到，从栈中弹出栈顶节点（回溯）
findUnvisitedNeighbor方法：
- 查找给定节点的第一个未访问邻接节点
- 如果没有未访问的邻接节点，返回-1

执行过程可视化

以示例中的图为例，从节点A(0)开始的DFS遍历过程如下：

访问A(0)，标记为已访问，入栈 [A]
A的未访问邻接节点是B(1)，访问B，标记为已访问，入栈 [A, B]
B的未访问邻接节点是D(3)，访问D，标记为已访问，入栈 [A, B, D]
D没有未访问的邻接节点，弹出D（回溯到B） [A, B]
B的下一个未访问邻接节点是E(4)，访问E，标记为已访问，入栈 [A, B, E]
E没有未访问的邻接节点，弹出E（回溯到B） [A, B]
B没有更多未访问的邻接节点，弹出B（回溯到A） [A]
A的下一个未访问邻接节点是C(2)，访问C，标记为已访问，入栈 [A, C]
C的未访问邻接节点是F(5)，访问F，标记为已访问，入栈 [A, C, F]
F没有未访问的邻接节点，弹出F（回溯到C） [A, C]
C的下一个未访问邻接节点是G(6)，访问G，标记为已访问，入栈 [A, C, G]
G没有未访问的邻接节点，弹出G（回溯到C） [A, C]
C没有更多未访问的邻接节点，弹出C（回溯到A） [A]
A没有更多未访问的邻接节点，弹出A，栈为空，遍历结束

最终的遍历顺序是：A B D E C F G

对Java初期学习的重要意义

1. 培养算法思维 🧠

学习DFS有助于培养解决复杂问题的算法思维。通过理解DFS的工作原理，你将学会如何将大问题分解为小问题，并通过回溯策略找到解决方案。这种思维方式对于解决各种编程挑战非常有价值！

2. 掌握递归和栈的应用 📚

DFS是递归和栈的经典应用场景。通过学习DFS，你可以深入理解递归的工作原理，以及如何使用栈来模拟递归过程。这些知识对于理解其他高级算法和数据结构至关重要。

3. 理解图论基础 🔍

DFS是图论中最基本的算法之一。掌握DFS后，你将更容易理解其他图算法，如广度优先搜索(BFS)、最短路径算法、最小生成树等。这为学习更复杂的图论知识奠定了基础。

4. 提高代码组织能力 📝

实现DFS需要良好的代码组织能力，特别是在处理复杂的图结构和状态管理时。这有助于提高你的代码质量和可维护性。

5. 解决实际问题的能力 💡

DFS在实际编程中有广泛的应用，从游戏开发到网络分析。掌握DFS后，你将能够解决许多实际问题，如迷宫寻路、网页爬虫、社交网络分析等。

总结

亲爱的同学们，今天我们一起深入探讨了深度优先搜索(DFS)这个强大的算法工具。🌟 我们学习了DFS的基本概念、实现方式、应用场景以及一些重要的注意事项。

DFS就像是一位勇敢的探险家，总是选择一条路径走到尽头，然后回头尝试其他路径。这种"一条路走到黑"的策略在解决许多问题时非常有效，特别是在需要找到所有可能解或检查图的连通性时。

记住，DFS有两种实现方式：递归和迭代。递归实现简洁优雅，但可能面临栈溢出的风险；迭代实现使用显式栈，更加灵活和安全。根据具体问题和约束条件，选择合适的实现方式非常重要。

在实际应用中，DFS可以帮助我们解决各种问题，从简单的图遍历到复杂的路径查找、拓扑排序和连通性分析。掌握DFS不仅能提高你的算法能力，还能培养解决复杂问题的思维方式。

希望这篇文章对你有所帮助！如果你有任何问题，欢迎在评论区留言讨论。学习是一个持续的过程，让我们一起在算法的世界中探索和成长吧！✨

记得点赞、收藏、分享哦！下期我们将继续探讨其他经典算法，敬请期待！👋

#算法学习 #深度优先搜索 #DFS #Java编程 #图论算法 #递归 #栈