深度优先搜索（DFS）：应用与实现

# 1. DFS 算法简介

深度优先搜索（Depth First Search，DFS）是一种常用的图搜索算法，它从图的某个顶点出发，沿着一条路一直往下搜寻直到底部，再返回沿着另一条路搜寻。在搜索过程中，尽可能深地搜索图中的分支，直到无法再继续为止，然后回溯到前一步。DFS 是一种用于遍历或搜索树或图的算法。

## 1.1 什么是深度优先搜索

深度优先搜索是一种用于遍历或搜索树、图等数据结构的基本算法。在进行深度优先搜索时，算法从根节点出发，沿着一个分支一直往下搜索，当搜索到无法再继续的节点时，算法回溯到前一步，继续搜索其他分支直到完成整个搜索。

## 1.2 DFS 的特点及应用场景

DFS 的特点包括深度优先、递归性、非常适合搜索全部解空间等。DFS 在很多领域都有着广泛的应用，比如图论中的连通性问题、树的遍历、路径搜索等场景都可以使用深度优先搜索来解决。

## 1.3 DFS 的工作原理

DFS 的基本原理是通过递归或栈来实现对图或树的深度搜索。首先访问起始顶点，然后选择一个相邻顶点进行访问，重复此过程直到无法再继续为止，然后回溯到前一步选择其他路径进行访问，直到完成整个搜索。

深度优先搜索是一种非常经典的搜索算法，具有简单、容易理解、易于实现等特点，在实际应用中具有广泛的价值。接下来，我们将深入探讨 DFS 的基本实现方式。

# 2. DFS 的基本实现

深度优先搜索（DFS）是一种重要的图算法，在解决各种实际问题中具有广泛的应用。本章将重点介绍DFS的基本实现方式，包括递归实现和栈实现两种方式。

#### 2.1 递归实现深度优先搜索

递归实现是DFS最常见的实现方式之一，其思路简单清晰，易于理解和编写。递归实现DFS的基本原理是：从起始节点开始，不断地访问其未访问过的相邻节点，直到所有可到达的节点都被访问过为止。

以下是Python语言的递归实现DFS的示例代码：

def dfs_recursive(graph, start, visited):
    if start not in visited:
        print(start, end=' ')
        visited.add(start)
        for neighbor in graph[start]:
            dfs_recursive(graph, neighbor, visited)

代码分析：
- 使用一个集合`visited`来存储已经访问过的节点，避免重复访问。
- 递归地访问起始节点未访问过的相邻节点，并将其加入`visited`集合中。

#### 2.2 栈实现深度优先搜索

另一种常见的DFS实现方式是使用栈结构来模拟递归过程，也称作非递归实现。这种方式在一些场景下性能更优，比如避免递归带来的函数调用开销和栈溢出问题。

以下是Java语言的栈实现DFS的示例代码：

import java.util.Stack;

public class DFS {
    public void dfsWithStack(Graph graph, int start) {
        boolean[] visited = new boolean[graph.getNumOfNodes()];
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited[node]) {
                System.out.print(node + " ");
                visited[node] = true; 
                for (int nei