龙空技术网

「超详细」深度优先搜索算法(DFS)

南秋同学 116

前言:

目前朋友们对“自由搜索算法有哪些”大体比较注重,小伙伴们都想要学习一些“自由搜索算法有哪些”的相关内容。那么小编在网络上收集了一些有关“自由搜索算法有哪些””的相关内容,希望小伙伴们能喜欢,朋友们快快来了解一下吧!

本章内容深度优先搜索

深度优先搜索(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领域,关注【南秋同学】带你一起学习成长~

标签: #自由搜索算法有哪些 #dfs 回溯 区别 #有向图dfs