devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

DFS(深度搜索)无向图遍历(JAVA手把手深入解析)_java dfs

作者：weixin_40725706 | 2024-04-23 21:26:40

赞

踩

java dfs

DFS(深度搜索)无向图遍历(JAVA手把手深入解析)

目录

DFS(深度搜索)无向图遍历(JAVA手把手深入解析)

前言

DFS深度优先

无向图

DFS全局变量定义 

1、节点

2、节点数

3、根据图创建数组

4、状态记录数组

四个全局变量

DFS代码

1、DFS启动·进入到递归搜索中

2、深度递归

节点控制（深搜核心）：

3、遍历节点

4、最终输出：

5、输出效果：

完整代码对照

总结

前言

        到了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】

public static String dian[] = { "1", "2", "3", "4", "5", "6", "7" };

2、节点数

我们所有的操作都会依赖于这个长度来进行遍历，故而这里我单独写了一下：

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】。

  1. 	public static int[][] arr= {
  2. 			{0,1,1,0,0,0,0},
  3. 			{1,0,0,1,1,0,0},
  4. 			{1,0,0,0,0,1,0},
  5. 			{0,1,0,0,0,0,1},
  6. 			{0,1,0,0,0,0,0},
  7. 			{0,0,1,0,0,0,0},
  8. 			{0,0,0,1,0,0,0},
  9. 	};

这样我们就把图形的规律记录成了一个长度为定点长度的二位数组。

4、状态记录数组

public static boolean[] isfStatus;

四个全局变量

这里我们共计创建了4个全局变量，依次是：

顶点、图转换数组、判断是否走过、记录每一个节点的遍历过程，走过则记录为true。

  1. /**                                                            
  2.  * 顶点                                                          
  3.  */                                                            
  4. public static String d[] = { "1", "2", "3", "4", "5", "6", "7" 
  5. /**                                                            
  6.  * 图转换数组                                                       
  7.  */                                                            
  8. public static int[][] arr= {                                   
  9. 		{0,1,1,0,0,0,0},                                       
  10. 		{1,0,0,1,1,0,0},                                       
  11. 		{1,0,0,0,0,1,0},                                       
  12. 		{0,1,0,0,0,0,1},                                       
  13. 		{0,1,0,0,0,0,0},                                       
  14. 		{0,0,1,0,0,0,0},                                       
  15. 		{0,0,0,1,0,0,0},                                       
  16. };                                                             
  17. /**                                                            
  18.  * 顶点长度
  19.  */                                                            
  20. public static int d_length=d.length;                           
  21. /**                                                            
  22.  * 记录每一个节点的遍历过程，走过则记录为true                                     
  23.  */                                                            
  24. public static boolean[] isfStatus;

这里我们所需要的变量就准备好了。

DFS代码

1、DFS启动·进入到递归搜索中

我们这里其实是注意行的深入，故而只要false就代表没有走过，我们需要遍历一下图，看看是否有对应的链接数组。

  1. /**                                                        
  2.  * 开始DFS
  3.  */                                                        
  4. public static void DFSStart() {                            
  5. 	//初始化数组，记录使用过程                                         
  6. 	isfStatus = new boolean[d_length];                     
  7. 	//遍历图数组                                                
  8. 	for (int i = 0; i < d_length; i++) {                   
  9. 		//因为初始的布尔数组都是false，所以只要是false就是没有走过                
  10. 		if (isfStatus[i] == false) {                       
  11. 			//进度到深度搜索的递归                                   
  12. 			DFS(i);                                        
  13. 		}                                                  
  14. 	}                                                      
  15. }

2、深度递归

我们这里需要注意的是深度搜索的节点遍历范围，我们从第一个开始，然后逐一遍历。

节点控制（深搜核心）：

从i行的列0开始遍历，只要有不是0的就代表有直接连接的，并且要找到的下层没有走过，也就是没有递归到，就开始判断。这里是核心。

  1. /**                                                       
  2.  * 递归深搜                                                   
  3.  * @param i                                               
  4.  */                                                       
  5. private static void DFS(int i) {                          
  6. 	// TODO Auto-generated method stub                    
  7. 	System.out.print(d[i] + " ");                         
  8. 	isfStatus[i] = true;                                  
  9. 	// 深度搜索子节点·从第一个节点到下一个节点                               
  10. 	for (int j = firstValue(i); j >= 0; j = nextValue(i, j)) {
  11. 		if (!isfStatus[j]) {                              
  12. 			DFS(j);                                       
  13. 		}                                                 
  14. 	}                                                     
  15. }

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来一层层的理解。

  1. /**                                           
  2.  * 第一个连接点                                     
  3.  * @param i                                   
  4.  * @return                                    
  5.  */                                           
  6. private static int firstValue(int i) {        
  7. 	for (int j = 0; j < d_length; j++) {      
  8. 		if (arr[i][j] > 0) {                  
  9. 			return j;                         
  10. 		}                                     
  11. 	}                                         
  12. 	return -1;                                
  13. }                                             
  14. /**                                           
  15.  * 下一个连接点                                     
  16.  * @param i                                   
  17.  * @param j                                   
  18.  * @return                                    
  19.  */                                           
  20. private static int nextValue(int i, int j) {  
  21. 	for (int k = (j + 1); k < d_length; k++) {
  22. 		if (arr[i][k] == 1) {                 
  23. 			return k;                         
  24. 		}                                     
  25. 	}                                         
  26. 	return -1;                                
  27. }

4、最终输出：

  1. public static void main(String[] args) {
  2. 	// TODO Auto-generated method stub
  3. 	DFSStart();
  4. }

5、输出效果：

可以看到，输出内容与我们的目标结果是相同的，代表我们深度搜索的编码没有问题。

完整代码对照

这个是我把类都复制了一下啊，你需要改一下包名以及你的类名即可进行测试。

  1. package com.item.action;
  2.  
  3. public class Demo_def {
  4. 	/**
  5. 	 * 顶点
  6. 	 */
  7. 	public static String d[] = { "1", "2", "3", "4", "5", "6", "7" };
  8. 	/**
  9. 	 * 图转换数组
  10. 	 */
  11. 	public static int[][] arr= {
  12. 			{0,1,1,0,0,0,0},
  13. 			{1,0,0,1,1,0,0},
  14. 			{1,0,0,0,0,1,0},
  15. 			{0,1,0,0,0,0,1},
  16. 			{0,1,0,0,0,0,0},
  17. 			{0,0,1,0,0,0,0},
  18. 			{0,0,0,1,0,0,0},
  19. 	};
  20. 	/**
  21. 	 * 顶点长度
  22. 	 */
  23. 	public static int d_length=d.length;
  24. 	/**
  25. 	 * 记录每一个节点的遍历过程，走过则记录为true
  26. 	 */
  27. 	public static boolean[] isfStatus;
  28. 	/**
  29. 	 * 开始递归
  30. 	 */
  31. 	public static void DFSStart() {
  32. 		//初始化数组，记录使用过程
  33. 		isfStatus = new boolean[d_length];
  34. 		//遍历图数组
  35. 		for (int i = 0; i < d_length; i++) {
  36. 			//因为初始的布尔数组都是false，所以只要是false就是没有走过
  37. 			if (isfStatus[i] == false) {
  38. 				//进度到深度搜索的递归
  39. 				DFS(i);
  40. 			}
  41. 		}
  42. 	}
  43. 	/**
  44. 	 * 递归深搜
  45. 	 * @param i
  46. 	 */
  47. 	private static void DFS(int i) {
  48. 		// TODO Auto-generated method stub
  49. 		System.out.print(d[i] + " ");
  50. 		isfStatus[i] = true;
  51. 		// 深度搜索子节点·从第一个节点到下一个节点
  52. 		for (int j = firstValue(i); j >= 0; j = nextValue(i, j)) {
  53. 			if (!isfStatus[j]) {
  54. 				DFS(j);
  55. 			}
  56. 		}
  57. 	}
  58. 	/**
  59. 	 * 第一个连接点
  60. 	 * @param i
  61. 	 * @return
  62. 	 */
  63. 	private static int firstValue(int i) {
  64. 		for (int j = 0; j < d_length; j++) {
  65. 			if (arr[i][j] > 0) {
  66. 				return j;
  67. 			}
  68. 		}
  69. 		return -1;
  70. 	}
  71. 	/**
  72. 	 * 下一个连接点
  73. 	 * @param i
  74. 	 * @param j
  75. 	 * @return
  76. 	 */
  77. 	private static int nextValue(int i, int j) {
  78. 		for (int k = (j + 1); k < d_length; k++) {
  79. 			if (arr[i][k] == 1) {
  80. 				return k;
  81. 			}
  82. 		}
  83. 		return -1;
  84. 	}
  85. 	public static void main(String[] args) {
  86. 		// TODO Auto-generated method stub
  87. 		DFSStart();
  88. 	}
  89.  
  90. }

完整代码留在这里是帮助大家对照的啊，别直接复制用，这样意义就不那么高了。

总结

        我们咋做蓝桥杯题的时候很多的时候都是有套路的，我们很多时候通过我们背过的一些套路去套题目也会直接出结果的，例如全排列的方法，还有很多的公式，欧几里得，欧拉等等，都是很方便的，我们其实不是算法的创造者，我们只是知识的搬运工，争取将更多的知识搬运到咱们的大脑中啊。

下一篇我会好好准备一下BFS深度搜索，大家好好用用心是可以完全搞定的，加油。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/476119
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号