Java实现深度搜索DFS算法详解

DFS简介

深度搜索（Depth First Search, DFS）是一种用于遍历或搜索树或图的算法。其基本思想是从根节点出发，尽可能深的遍历每一个节点，直到没有下一个未访问的节点，然后回溯到最近的未访问节点，并继续访问其它节点。

DFS算法流程

DFS算法的流程如下：

1. 将起始节点添加到栈中
2. 判断栈是否为空，如果为空则退出搜索
3. 从栈中取出一个节点
4. 判断该节点是否为目标节点，如果是则搜索结束
5. 如果不是目标节点，则将所有与该节点相邻的未访问节点添加到栈中，并标记为已访问
6. 回到步骤2

Java实现DFS算法

下面是一个Java实现DFS算法的示例，假设有一个图G和起始节点S：

import java.util.Stack;

public class DFS {
    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        graph.addEdge(4, 2);
        graph.addEdge(4, 5);
        dfs(graph, 0);
    }

    public static void dfs(Graph graph, int startNode) {
        boolean[] visited = new boolean[graph.nodes.length];
        Stack<Integer> stack = new Stack<>();
        stack.push(startNode);
        visited[startNode] = true;
        while (!stack.empty()) {
            int currentNode = stack.pop();
            System.out.print(currentNode + " ");
            for (int i = 0; i < graph.nodes[currentNode].size(); i++) {
                int nextNode = graph.nodes[currentNode].get(i);
                if (!visited[nextNode]) {
                    stack.push(nextNode);
                    visited[nextNode] = true;
                }
            }
        }
    }
}

class Graph {
    int v;
    LinkedList<Integer>[] nodes;

    public Graph(int v) {
        this.v = v;
        nodes = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            nodes[i] = new LinkedList<>();
        }
    }

    public void addEdge(int start, int end) {
        nodes[start].add(end);
    }
}

上述代码中定义了一个Graph类，用于存储节点和边的信息。dfs方法中的visited数组用于记录节点是否被访问过，stack用于存储遍历的节点，startNode为起点。

执行结果为：0 2 3 4 5 1。从起始节点0开始遍历，先访问0，然后将与0相邻且未访问节点2加入栈，此时栈为[2]，继续访问2，将与2相邻且未访问节点3和4加入栈，此时栈为[4, 3]，访问4，将与4相邻且未访问节点5加入栈，此时栈为[3, 5]，依次访问节点5、节点3，发现没有未访问节点，返回到节点2，将与2相邻且未访问节点1加入栈，此时栈为[1]，访问节点1并结束搜索。

下面是另一个示例，假设有一个迷宫图maze：

import java.util.Arrays;

public class DFS {
    public static void main(String[] args) {
        int[][] maze = {
                {1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 0, 1, 0, 0, 0, 0, 0, 1},
                {1, 0, 1, 1, 1, 0, 1, 0, 1},
                {1, 0, 0, 0, 1, 0, 1, 0, 1},
                {1, 0, 1, 1, 1, 0, 1, 0, 1},
                {1, 0, 1, 0, 0, 0, 1, 0, 1},
                {1, 0, 1, 1, 1, 1, 1, 0, 1},
                {1, 0, 0, 0, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1}
        };
        dfs(maze, 1, 1, 7, 7);
    }

    public static void dfs(int[][] maze, int startX, int startY, int endX, int endY) {
        int[][] visited = new int[maze.length][maze[0].length];
        for (int[] row : visited) Arrays.fill(row, -1);

        Stack<Point> stack = new Stack<>();
        stack.push(new Point(startX, startY));
        visited[startX][startY] = 0;

        int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!stack.empty()) {
            Point currentPoint = stack.pop();
            for (int i = 0; i < 4; i++) {
                int nextX = currentPoint.x + direction[i][0];
                int nextY = currentPoint.y + direction[i][1];
                if (nextX < 0 || nextY < 0 || nextX >= maze.length || nextY >= maze[0].length) continue;
                if (maze[nextX][nextY] == 1 || visited[nextX][nextY] != -1) continue;
                visited[nextX][nextY] = visited[currentPoint.x][currentPoint.y] + 1;
                stack.push(new Point(nextX, nextY));
            }
        }

        System.out.println(visited[endX][endY]);
    }

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

上述代码中定义了一个Point类，用于存储x,y的坐标信息，这是一个典型的迷宫问题。执行结果为：22。

从起点(1,1)开始遍历，先访问(1,1)，然后将与(1,1)相邻且未访问的点(2,1)、(1,2)加入栈，此时栈为[(2,1),(1,2)]，访问(2,1)，将与(2,1)相邻且未访问的点(3,1)加入栈，此时栈为[(1,2),(3,1)]，继续访问(1,2)，将(1,3)加入栈，此时栈为[(3,1),(1,3)]，访问(3,1)，将(4,1)加入栈，此时栈为[(1,3),(4,1)]，依次访问(1,3)、(4,1)、(5,1)、(6,1)、(6,2)、(6,3)、(6,4)、(5,4)、(4,4)、(3,4)、(2,4)、(2,3)、(2,2)、(3,2)、(3,3)、(4,3)、(5,3)、(5,2)、(4,2)、(4,3)、(4,4)、(5,4)、(6,4)、(6,5)、(6,6)、(5,6)、(4,6)、(3,6)、(2,6)、(1,6)、(1,7)、(2,7)、(3,7)、(4,7)、(5,7)、(6,7)、(7,7)、(7,6)、(7,5)、(7,4)、(7,3)、(7,2)、(7,1)，发现已到达终点(7,7)，返回22。