「超详细」深度优先搜索算法（DFS）

欢迎大家来到IT世界,在知识的湖畔探索吧!

本章内容

欢迎大家来到IT世界,在知识的湖畔探索吧!

深度优先搜索

深度优先搜索（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); } }

欢迎大家来到IT世界,在知识的湖畔探索吧!

复杂度

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

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

【阅读推荐】

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

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

更多内容持续更新中……

【作者简介】

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