| DFS(深度搜索)无向图遍历(JAVA手把手深入解析) | 您所在的位置：网站首页 › 图的dfs遍历 › DFS(深度搜索)无向图遍历(JAVA手把手深入解析) |
DFS(深度搜索)无向图遍历(JAVA手把手深入解析)
 前言到了DFS与BFS这里就是一个省一的分界线了，能搞定的省一基本没有问题，当然，也有靠纯暴力进入省一的，但是几率就会小一些。这篇文章我已经将DFS拆分的很细了呢，希望能帮助大家跨过蓝桥杯的这个分水岭。 如果帮助到了你，请留下你的三连支持。 DFS深度优先深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。  图中的深度结果就是：0->1->3->4->2 这是深度搜索DFS的遍历方式。 我们已经知道DFS是怎么个逻辑了，那么我们就画一个图做个DFS的搜索。(图随便画，一会自己能根据深度搜索的理论把对应的数组写出来就行)。 无向图这里我们来自己画。画的跟树类似，可以使用类创建左右孩子的方式来解决，但是咱们为了更好的让大一的孩子们理解，所以用一个类来决绝这个问题。  途中我们依照DFS深度搜索的方式目标输出结果是：1->2->4->7->5->3->6。我们接下来就开始我们的编码，看看是否能按照这个DFS的方式进行遍历。 DFS全局变量定义 1、节点为了帮助孩子们理解，我这里使用的是拼音拼写的变量【dian】 代码语言：javascript复制public static String dian[] = { "1", "2", "3", "4", "5", "6", "7" };2、节点数我们所有的操作都会依赖于这个长度来进行遍历，故而这里我单独写了一下： 代码语言：javascript复制public static int d_length=d.length;3、根据图创建数组我们用二位数组来表达我们的输出顺序。 1的关联方式是：1列链接1,3故而有数组{0,1,1,0,0,0,0}来表示【1】，那么，同理我们依次推导出2~7的数组表达。 挨个根据图来写，只要有链接就记录一个【1】，没有链接就记录【0】，自身遇到自身记录【0】。 代码语言：javascript复制 public static int[][] arr= { {0,1,1,0,0,0,0}, {1,0,0,1,1,0,0}, {1,0,0,0,0,1,0}, {0,1,0,0,0,0,1}, {0,1,0,0,0,0,0}, {0,0,1,0,0,0,0}, {0,0,0,1,0,0,0}, };这样我们就把图形的规律记录成了一个长度为定点长度的二位数组。 4、状态记录数组代码语言：javascript复制public static boolean[] isfStatus;四个全局变量这里我们共计创建了4个全局变量，依次是： 顶点、图转换数组、判断是否走过、记录每一个节点的遍历过程，走过则记录为true。 代码语言：javascript复制/** * 顶点 */ public static String d[] = { "1", "2", "3", "4", "5", "6", "7" /** * 图转换数组 */ public static int[][] arr= { {0,1,1,0,0,0,0}, {1,0,0,1,1,0,0}, {1,0,0,0,0,1,0}, {0,1,0,0,0,0,1}, {0,1,0,0,0,0,0}, {0,0,1,0,0,0,0}, {0,0,0,1,0,0,0}, }; /** * 顶点长度 */ public static int d_length=d.length; /** * 记录每一个节点的遍历过程，走过则记录为true */ public static boolean[] isfStatus;这里我们所需要的变量就准备好了。 DFS代码1、DFS启动·进入到递归搜索中我们这里其实是注意行的深入，故而只要false就代表没有走过，我们需要遍历一下图，看看是否有对应的链接数组。 代码语言：javascript复制/** * 开始DFS */ public static void DFSStart() { //初始化数组，记录使用过程 isfStatus = new boolean[d_length]; //遍历图数组 for (int i = 0; i < d_length; i++) { //因为初始的布尔数组都是false，所以只要是false就是没有走过 if (isfStatus[i] == false) { //进度到深度搜索的递归 DFS(i); } } } 2、深度递归我们这里需要注意的是深度搜索的节点遍历范围，我们从第一个开始，然后逐一遍历。 节点控制（深搜核心）：从i行的列0开始遍历，只要有不是0的就代表有直接连接的，并且要找到的下层没有走过，也就是没有递归到，就开始判断。这里是核心。 代码语言：javascript复制/** * 递归深搜 * @param i */ private static void DFS(int i) { // TODO Auto-generated method stub System.out.print(d[i] + " "); isfStatus[i] = true; // 深度搜索子节点·从第一个节点到下一个节点 for (int j = firstValue(i); j >= 0; j = nextValue(i, j)) { if (!isfStatus[j]) { DFS(j); } } } 3、遍历节点这里能看到我写了两个判断，判断1是arr[i][j]>0，还有第二个判断arr[i][k] == 1其实都是一样的，因为咱们的数组当中只有1与0两个，大于零是1，等等于1还是1，所以是一样的。 全局控制：变量【i】，我们通过变量【i】来控制我们遍历的行数，这样就能逐一击破了。 初始点：坐标点需要从最左侧的0开始遍历，只要找到不是0的数就代表有链接点了。 下一个链接：坐标得从第N个开始遍历了，因为之前的已经遍历过了。这里的N是变量【j】。 我们这里再加强一下理解： 先看【第一个连接点】，例如图中的【1】与【2,3】相连，我们遍历到2的时候也就是坐标【arr[0][1]】就代表1与2相连接，我们在继续向下层递归，也就是i向下走一层【DFS(i)】也就下一个有相关链接的点。有难度的时候我们可以通过debug来一层层的理解。 代码语言：javascript复制/** * 第一个连接点 * @param i * @return */ private static int firstValue(int i) { for (int j = 0; j < d_length; j++) { if (arr[i][j] > 0) { return j; } } return -1; } /** * 下一个连接点 * @param i * @param j * @return */ private static int nextValue(int i, int j) { for (int k = (j + 1); k < d_length; k++) { if (arr[i][k] == 1) { return k; } } return -1; } 4、最终输出：代码语言：javascript复制public static void main(String[] args) { // TODO Auto-generated method stub DFSStart(); }5、输出效果：可以看到，输出内容与我们的目标结果是相同的，代表我们深度搜索的编码没有问题。  完整代码对照这个是我把类都复制了一下啊，你需要改一下包名以及你的类名即可进行测试。 代码语言：javascript复制package com.item.action; public class Demo_def { /** * 顶点 */ public static String d[] = { "1", "2", "3", "4", "5", "6", "7" }; /** * 图转换数组 */ public static int[][] arr= { {0,1,1,0,0,0,0}, {1,0,0,1,1,0,0}, {1,0,0,0,0,1,0}, {0,1,0,0,0,0,1}, {0,1,0,0,0,0,0}, {0,0,1,0,0,0,0}, {0,0,0,1,0,0,0}, }; /** * 顶点长度 */ public static int d_length=d.length; /** * 记录每一个节点的遍历过程，走过则记录为true */ public static boolean[] isfStatus; /** * 开始递归 */ public static void DFSStart() { //初始化数组，记录使用过程 isfStatus = new boolean[d_length]; //遍历图数组 for (int i = 0; i < d_length; i++) { //因为初始的布尔数组都是false，所以只要是false就是没有走过 if (isfStatus[i] == false) { //进度到深度搜索的递归 DFS(i); } } } /** * 递归深搜 * @param i */ private static void DFS(int i) { // TODO Auto-generated method stub System.out.print(d[i] + " "); isfStatus[i] = true; // 深度搜索子节点·从第一个节点到下一个节点 for (int j = firstValue(i); j >= 0; j = nextValue(i, j)) { if (!isfStatus[j]) { DFS(j); } } } /** * 第一个连接点 * @param i * @return */ private static int firstValue(int i) { for (int j = 0; j < d_length; j++) { if (arr[i][j] > 0) { return j; } } return -1; } /** * 下一个连接点 * @param i * @param j * @return */ private static int nextValue(int i, int j) { for (int k = (j + 1); k < d_length; k++) { if (arr[i][k] == 1) { return k; } } return -1; } public static void main(String[] args) { // TODO Auto-generated method stub DFSStart(); } }完整代码留在这里是帮助大家对照的啊，别直接复制用，这样意义就不那么高了。 总结我们咋做蓝桥杯题的时候很多的时候都是有套路的，我们很多时候通过我们背过的一些套路去套题目也会直接出结果的，例如全排列的方法，还有很多的公式，欧几里得，欧拉等等，都是很方便的，我们其实不是算法的创造者，我们只是知识的搬运工，争取将更多的知识搬运到咱们的大脑中啊。 下一篇我会好好准备一下BFS深度搜索，大家好好用用心是可以完全搞定的，加油。 |
【本文地址】