深度优先搜索（DFS）：从入门到精通！

深度优先搜索（DFS）：从入门到精通！

引用

CSDN

1.

https://m.blog.csdn.net/2301_78858041/article/details/145780554

深度优先搜索（DFS）是一种经典的图遍历算法，在解决路径查找、迷宫问题、拓扑排序等问题中发挥着重要作用。无论你是编程小白还是有一定经验的开发者，这篇文章都将带你一步步掌握 DFS 的核心概念和实现方法！

一、深度优先搜索（DFS）：基础篇

1.1 DFS 的定义

深度优先搜索（Depth-First Search，简称 DFS）是一种用于遍历树或图的算法。它的核心思想是尽可能“深入”访问图的每个节点，直到无法继续前进为止，然后再回溯到之前的节点继续遍历。

1.2 DFS 的工作原理

DFS 的基本步骤如下：

1. 访问当前节点：从起点节点开始访问。
2. 递归遍历子节点：依次访问当前节点的所有未被访问过的子节点。
3. 回溯：当所有子节点都被访问完毕后，回溯到父节点继续遍历。

1.3 DFS 的典型应用场景

• 迷宫求解：寻找从起点到终点的路径。
• 连通性问题：判断图中的两个节点是否连通。
• 拓扑排序：对有向无环图（DAG）进行拓扑排序。
• 路径查找：在图中查找从一个节点到另一个节点的所有可能路径。

二、DFS 的实现方式

2.1 递归实现

递归是实现 DFS 最直观的方式。通过递归函数，我们可以轻松地模拟 DFS 的回溯过程。

代码示例：递归实现 DFS

import java.util.ArrayList;
import java.util.List;

public class DFSDemo {
    // 定义一个图结构
    private List<List<Integer>> graph;

    public DFSDemo(int numNodes) {
        graph = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            graph.add(new ArrayList<>());
        }
    }

    // 添加边
    public void addEdge(int u, int v) {
        graph.get(u).add(v);
    }

    // 递归实现 DFS
    public void dfsRecursive(int startNode, boolean[] visited) {
        // 标记当前节点为已访问
        visited[startNode] = true;
        System.out.print(startNode + " ");

        // 递归访问所有未被访问的邻接节点
        for (int neighbor : graph.get(startNode)) {
            if (!visited[neighbor]) {
                dfsRecursive(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        // 创建一个包含 5 个节点的图
        DFSDemo dfsDemo = new DFSDemo(5);
        dfsDemo.addEdge(0, 1);
        dfsDemo.addEdge(0, 2);
        dfsDemo.addEdge(1, 3);
        dfsDemo.addEdge(2, 3);
        dfsDemo.addEdge(3, 4);

        boolean[] visited = new boolean[5];
        System.out.println("DFS Traversal starting from node 0:");
        dfsDemo.dfsRecursive(0, visited);
    }
}

运行上述代码后，输出结果为：

DFS Traversal starting from node 0:
0 1 3 4 2

2.2 非递归实现

为了避免递归带来的栈溢出问题，我们可以通过栈数据结构实现非递归版本的 DFS。

代码示例：非递归实现 DFS

import java.util.Stack;

public class DFSDemoNonRecursive {
    // 定义一个图结构
    private List<List<Integer>> graph;

    public DFSDemoNonRecursive(int numNodes) {
        graph = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            graph.add(new ArrayList<>());
        }
    }

    // 添加边
    public void addEdge(int u, int v) {
        graph.get(u).add(v);
    }

    // 非递归实现 DFS
    public void dfsNonRecursive(int startNode) {
        boolean[] visited = new boolean[graph.size()];
        Stack<Integer> stack = new Stack<>();

        // 初始化栈
        stack.push(startNode);
        visited[startNode] = true;

        while (!stack.isEmpty()) {
            // 弹出栈顶元素
            int currentNode = stack.pop();
            System.out.print(currentNode + " ");

            // 将当前节点的所有邻接节点入栈
            for (int neighbor : graph.get(currentNode)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        // 创建一个包含 5 个节点的图
        DFSDemoNonRecursive dfsDemo = new DFSDemoNonRecursive(5);
        dfsDemo.addEdge(0, 1);
        dfsDemo.addEdge(0, 2);
        dfsDemo.addEdge(1, 3);
        dfsDemo.addEdge(2, 3);
        dfsDemo.addEdge(3, 4);

        System.out.println("DFS Traversal starting from node 0:");
        dfsDemo.dfsNonRecursive(0);
    }
}

运行上述代码后，输出结果同样为：

DFS Traversal starting from node 0:
0 1 3 4 2

三、DFS 的实际应用案例

3.1 案例 1：迷宫求解

3.1.1 案例背景
假设我们有一个迷宫，需要用 DFS 找出从起点到终点的路径。

3.1.2 实现步骤

1. 构建迷宫的图结构
2. 使用 DFS 遍历迷宫
3. 记录路径并输出结果

3.1.3 代码实现

import java.util.ArrayList;
import java.util.List;

public class MazeSolver {
    // 定义迷宫的方向：上、下、左、右
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 迷宫的行数和列数
    private int rows;
    private int cols;

    // 记录访问情况
    private boolean[][] visited;

    // 记录路径
    private List<int[]> path;

    public MazeSolver(int[][] maze) {
        this.rows = maze.length;
        this.cols = maze[0].length;
        this.visited = new boolean[rows][cols];
        this.path = new ArrayList<>();
    }

    // 检查当前位置是否有效
    private boolean isValid(int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols && !visited[x][y] && maze[x][y] == 0;
    }

    // DFS 寻找迷宫出口
    public boolean solveMaze(int startX, int startY, int endX, int endY) {
        if (startX == endX && startY == endY) {
            return true;
        }

        // 标记当前位置为已访问
        visited[startX][startY] = true;
        path.add(new int[]{startX, startY});

        // 遍历四个方向
        for (int[] dir : DIRECTIONS) {
            int newX = startX + dir[0];
            int newY = startY + dir[1];

            if (isValid(newX, newY)) {
                if (solveMaze(newX, newY, endX, endY)) {
                    return true;
                }
            }
        }

        // 回溯
        visited[startX][startY] = false;
        path.remove(path.size() - 1);
        return false;
    }

    public static void main(String[] args) {
        // 创建一个迷宫
        int[][] maze = {
            {0, 1, 0, 0},
            {0, 1, 0, 1},
            {0, 0, 0, 0},
            {1, 1, 1, 0}
        };

        MazeSolver solver = new MazeSolver(maze);
        boolean solved = solver.solveMaze(0, 0, 3, 3);

        if (solved) {
            System.out.println("Path found:");
            for (int[] point : solver.path) {
                System.out.println("(" + point[0] + ", " + point[1] + ")");
            }
        } else {
            System.out.println("No path exists.");
        }
    }
}

运行上述代码后，输出结果为：

Path found:
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(3, 2)
(3, 3)

3.2 案例 2：拓扑排序

3.2.1 案例背景
拓扑排序是将有向无环图（DAG）中的节点按某种顺序排列，使得对于每一条有向边 u → v，u 在排列中出现在 v 之前。

3.2.2 实现步骤

1. 构建图的邻接表
2. 计算每个节点的入度
3. 使用 DFS 进行拓扑排序

3.2.3 代码实现

import java.util.ArrayList;
import java.util.List;

public class TopologicalSort {
    private List<List<Integer>> graph;
    private int[] inDegree;

    public TopologicalSort(int numNodes) {
        graph = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            graph.add(new ArrayList<>());
        }
        inDegree = new int[numNodes];
    }

    // 添加边
    public void addEdge(int u, int v) {
        graph.get(u).add(v);
        inDegree[v]++;
    }

    // 拓扑排序
    public void topologicalSort() {
        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[graph.size()];

        for (int i = 0; i < graph.size(); i++) {
            if (!visited[i]) {
                dfsTopo(i, visited, result);
            }
        }

        System.out.println("Topological Order: " + result);
    }

    // DFS 辅助函数
    private void dfsTopo(int node, boolean[] visited, List<Integer> result) {
        visited[node] = true;

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfsTopo(neighbor, visited, result);
            }
        }

        result.add(node);
    }

    public static void main(String[] args) {
        TopologicalSort topoSort = new TopologicalSort(6);
        topoSort.addEdge(5, 2);
        topoSort.addEdge(5, 0);
        topoSort.addEdge(4, 5);
        topoSort.addEdge(4, 3);
        topoSort.addEdge(2, 3);
        topoSort.addEdge(3, 1);

        topoSort.topologicalSort();
    }
}

运行上述代码后，输出结果为：

Topological Order: [4, 5, 2, 3, 1, 0]

四、常见问题解答

Q1：DFS 和 BFS 的区别是什么？
A1：DFS 是深度优先，倾向于先访问最深层的节点；而 BFS 是广度优先，倾向于先访问同一层的所有节点。

Q2：DFS 是否一定会找到最短路径？
A2：不一定。DFS 更关注深度优先，而不是最短路径。要找最短路径应使用 BFS。

Q3：如何避免 DFS 中的无限循环？
A3：通过标记已访问的节点，并确保每个节点只被访问一次。