前言:
目前朋友们对“自由搜索算法有哪些”大体比较注重,小伙伴们都想要学习一些“自由搜索算法有哪些”的相关内容。那么小编在网络上收集了一些有关“自由搜索算法有哪些””的相关内容,希望小伙伴们能喜欢,朋友们快快来了解一下吧!本章内容深度优先搜索
深度优先搜索(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领域,关注【南秋同学】带你一起学习成长~