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

简介: 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】

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

相关文章
|
8天前
|
Java
Java中ReentrantLock释放锁代码解析
Java中ReentrantLock释放锁代码解析
25 8
|
6天前
|
Java
Java 15 神秘登场:隐藏类解析未知领域
Java 15 神秘登场:隐藏类解析未知领域
10 0
|
6天前
|
安全 Java 编译器
接口之美,内部之妙:深入解析Java的接口与内部类
接口之美,内部之妙:深入解析Java的接口与内部类
25 0
接口之美,内部之妙:深入解析Java的接口与内部类
|
24天前
|
Java 程序员 C#
静态构造方法解析,Java新手必看技能
静态构造方法解析,Java新手必看技能
8 0
|
28天前
|
XML Java 数据格式
使用java解析XML文件的步骤
使用java解析XML文件的步骤
10 0

推荐镜像

更多