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

举报
红目香薰 发表于 2023/02/13 16:48:23 2023/02/13
【摘要】 DFS(深度搜索)无向图遍历(JAVA手把手深入解析) 前言 DFS深度优先 无向图 DFS全局变量定义 1、节点 2、节点数 3、根据图创建数组 4、状态记录数组 四个全局变量 DFS代码 1、DFS启动·进入到递归搜索中 2、深度递归 节点控制(深搜核心): 3、遍历节点 4、最终输出: 5、输出效果: 完整代码对照 总结

 编辑

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

	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、状态记录数组

public static boolean[] isfStatus;

四个全局变量

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

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

/**                                                            
 * 顶点                                                          
 */                                                            
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就代表没有走过,我们需要遍历一下图,看看是否有对应的链接数组。

/**                                                        
 * 开始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的就代表有直接连接的,并且要找到的下层没有走过,也就是没有递归到,就开始判断。这里是核心。

/**                                                       
 * 递归深搜                                                   
 * @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来一层层的理解。

/**                                           
 * 第一个连接点                                     
 * @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、最终输出:

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

5、输出效果:

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

编辑

完整代码对照

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

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深度搜索,大家好好用用心是可以完全搞定的,加油。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。