本章内容

深度优先搜索

深度优先搜索（Depth-First-Search，简称DFS）是一种基于图或搜索树的算法，从起始顶点开始选择某一路径深度试探查找目标顶点，当该路径上不存在目标顶点时，回溯到起始顶点继续选择另一条路径深度试探查找目标顶点，直到找到目标顶点或试探完所有顶点后回溯到起始顶点，完成搜索。

由于DFS是以后进先出的方式遍历顶点，因此，可以使用栈（stack）存储已经被搜索、相连顶点还未被搜索的顶点。

DFS的核心思想：回溯和剪枝。

图解DFS

如图所示：

图中，s表示起始顶点，t表示目标顶点，求解从s->t的搜索路径（注意：不是最短路径）。

搜索步骤：

1.搜索邻接表中顶点0对应的链表：

• 1）将顶点0压入栈中，设置visited数组中顶点0（下标）的元素值为1（即：true）。
• 2）判断顶点0是否为目标顶点，是则完成搜索；否则从前往后遍历邻接表中顶点0对应链表的节点：1->3，判断顶点1是否被搜索过（即：visited数组中顶点1（下标）对应的元素值是否为true）。
• 3）顶点1未被搜索过，则将顶点1压入栈中，并设置route数组中顶点1（下标）对应的元素值为源顶点（即：顶点0）。

如图所示：

2.搜索邻接表中顶点1对应的链表：

• 1）将顶点1压入栈中，设置visited数组中顶点1（下标）的元素值为1（即：true）。
• 2）判断顶点1是否为目标顶点，是则沿搜索路径回溯到起始顶点，完成搜索；否则从前往后遍历邻接表中顶点1对应链表的节点：0->2->4，其中顶点0已经被搜索过。
• 3）顶点2未被搜索过，则将顶点2压入栈中，并设置route数组中顶点2（下标）对应的元素值为源顶点（即：顶点1）。

如图所示：

3.搜索邻接表中顶点2对应的链表：

• 1）将顶点2压入栈中，设置visited数组中顶点2（下标）的元素值为1（即：true）。
• 2）判断顶点2是否为目标顶点，是则沿搜索路径回溯到起始顶点，完成搜索；否则从前往后遍历邻接表中顶点2对应链表的节点：1->5，其中顶点1已经被搜索过。
• 3）顶点5未被搜索过，则将顶点5压入栈中，并设置route数组中顶点5（下标）对应的元素值为源顶点（即：顶点2）。

如图所示：

4.搜索邻接表中顶点5对应的链表：

• 1）将顶点5压入栈中，设置visited数组中顶点5（下标）的元素值为1（即：true）。
• 2）判断顶点5是否为目标顶点，是则沿搜索路径回溯到起始顶点，完成搜索；否则从前往后遍历邻接表中顶点5对应链表的节点：2->4->7，其中顶点2已经被搜索过。
• 3）顶点4未被搜索过，则将顶点4压入栈中，并设置route数组中顶点4（下标）对应的元素值为源顶点（即：顶点5）。

如图所示：

5.搜索邻接表中顶点4对应的链表：

• 1）将顶点4压入栈中，设置visited数组中顶点4（下标）的元素值为1（即：true）。
• 2）判断顶点4是否为目标顶点，是则沿搜索路径回溯到起始顶点，完成搜索；否则从前往后遍历邻接表中顶点4对应链表的节点：1->3->5->6，其中顶点1已经被搜索过。
• 3）顶点3未被搜索过，则将顶点3压入栈中，并设置route数组中顶点3（下标）对应的元素值为源顶点（即：顶点4）。

如图所示：

6.搜索邻接表中顶点3对应的链表：

• 1）将顶点3压入栈中，设置visited数组中顶点3（下标）的元素值为1（即：true）。
• 2）判断顶点3是否为目标顶点，是则沿搜索路径回溯到起始顶点，完成搜索；否则从前往后遍历邻接表中顶点3对应链表的节点：0->4，其中顶点0、4都已经被搜索过，回溯到顶点4，继续遍历邻接表中顶点4对应链表的剩余节点：5->6，其中顶点5也已经被搜索过。
• 3）顶点6未被搜索过，则将顶点6压入栈中，并设置route数组中顶点6（下标）对应的元素值为源顶点（即：顶点4）。

当前顶点6为要查找的目标顶点，开始根据栈中顶点的入栈顺序反向回溯（即：将栈中的顶点按顺序从栈中弹出），一直回溯到起始顶点0，完成搜索。

如图所示：

最终搜索路径为：0->1->2->5->4->6 。

总体搜索过程如图所示：

其中：

• 实现：表示正向搜索。
• 虚线：表示反向回溯。

代码实现

/**
 * @author 南秋同学
 * 深度优先搜索算法
 */
public class Dfs {
    /**
     * 图中节点数
     */
    private final int number;
    /**
     * 采用邻接表存储图
     */
    private final LinkedList<Integer>[] adjacencyList;


    public Dfs(int number){
        this.number = number;
        adjacencyList = new LinkedList[number];
        for(int i=0; i<number; ++i){
            adjacencyList[i] = new LinkedList<>();
        }
    }
    /**
     * 增加一条边(无向图一条边存两次)
     * @param start 节点
     * @param target 节点
     */
    public void addEdge(int start, int target){
        adjacencyList[start].add(target);
        adjacencyList[target].add(start);
    }


    /**
     * 是否找到目标顶点标识
     */
    boolean found = false;
    /**
     * 深度优先搜索算法
     * @param start 起始顶点
     * @param target 目标顶点
     */
    public void dfs(int start, int target) {
        // 初始化木是否找到目标顶点标识
        found = false;
        // 初始化记录已经被搜索顶点的数组
        boolean[] visited = new boolean[number];
        // 初始化路径存储数组
        int[] route = new int[number];
        for (int i = 0; i < number; ++i) {
            route[i] = -1;
        }
        // 递归搜索目标顶点（相当于栈）
        recursionDfs(start, target, visited, route);
        // 打印路径
        print(route, start, target);
    }


    private void recursionDfs(int start, int target, boolean[] visited, int[] route) {
        if (found) {
            return;
        }
        // 记录已经被搜索顶点
        visited[start] = true;
        // 判断当前顶点是否为目标顶点，是则设置found标识为true（找到目标顶点）
        if (start == target) {
            found = true;
            return;
        }
        // 遍历与当前顶点相连的所有顶点
        for (int i = 0; i < adjacencyList[start].size(); ++i) {
            int q = adjacencyList[start].get(i);
            // 判断与当前顶点相连的顶点是否已经被搜索过
            if (!visited[q]) {
                // 记录当前顶点路径
                route[q] = start;
                // 递归遍历后继与当前顶点相连、未被搜索过的顶点
                recursionDfs(q, target, visited, route);
            }
        }
    }


    /**
     * 递归打印s->t的路径
     * @param route 路径
     * @param start 起始顶点
     * @param target 目标顶点
     */
    private void print(int[] route, int start, int target) {
        if (route[target] != -1 && target != start) {
            print(route, start, route[target]);
        }
        System.out.print(target + " ");
    }


    public static void main(String[] args) {
        Dfs dfs = new Dfs(8);
        // 构建图
        dfs.addEdge(0,1);
        dfs.addEdge(0,3);
        dfs.addEdge(1,2);
        dfs.addEdge(1,4);
        dfs.addEdge(3,4);
        dfs.addEdge(2,5);
        dfs.addEdge(4,5);
        dfs.addEdge(4,6);
        dfs.addEdge(5,7);
        dfs.addEdge(6,7);
        // 求解0～6的最短路径
        dfs.dfs(0,6);
    }
}

复杂度

深度优先搜索算法的时间复杂度为O(E)，E表示边的条数。

深度优先搜索算法的空间复杂度为O(V)，V表示顶点个数。

【阅读推荐】

对本文中描述的图不了解的童鞋请移步算法系列合集中的「一发入魂」广度优先算法（BFS）章节。

想了解其他常用算法（如：快速排序、堆与堆排序、二分查找、动态规划、带备忘录的递归、暴力穷举、广度优先算法（BFS）等）的童鞋请移步->算法系列合集（持续更新中）。

更多内容持续更新中......

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～