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

java--DFS深度搜索方法_java dfs

作者：你好赵伟 | 2024-04-23 21:25:16

赞

踩

java dfs

参考文章，原文链接：(5条消息) DFS(深度搜索)无向图遍历(JAVA手把手深入解析)_红目香薰的博客-CSDN博客

部分图片，代码 来自参考文章

DFS（深度搜索）方法理论与理解

节点：即图中包含数字的点，对应代码的数据

深度搜索就是：

从指定节点开始，一直向一个方向走，直到没有路

在有下一级的节点（也就是有链接的节点），我们可以向任意下级节点（没有被遍历过的）出发，还是直到没有下级，

如果没有下一级，就返回，返回到 最近的（上一个） 有未曾遍历的下级节点 的节点，

然后进入到那个未曾遍历的节点方向

输出顺序就是遍历顺序（经过顺序）

下面有手写的流程，可以参考对照，便于理解

DFS方法的实现

数据准备，数据输入

我们需要四个全局变量，全局变量！！！

这里的数据都是以上面的为例子

1，节点数，所有节点的记录

dian即节点（方便理解，随意命名可以），类型为需要的类型，

需要将每一个节点录入该数组，顺序可以随意（下面的二维图转换数组的顺序需要对照这个循序，所以晴考虑一下）

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

2、全节点数，数组长度、节点数量的记录

即所有节点的数量，

下面会按照这个长度来遍历，就是上面数组的长度，

直接定义也许， .length也许

public static int dian_length=dian.length;

3、二维数组，链接关系的记录

这个数组可以存储，每一个节点 所链接的节点都有哪些（包括上、下级）；

创建的规则：

，如果有n给节点，就创建n*n的二维数组，

、第n行必须对应 节点数组 的 第n个节点

标注规则：

链接到对应的节点就标注 1

没有链接对应节点就标注 0

如果对应的节点是自身标注 0

看下面就一下明白了，，，，，.

这里用示例包含7个节点，所以7*7的二维数组

  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、布尔数组，是否遍历的记录

从对方法的理解中，我们知道，再没有下级节点的时候，我们需要返回

并且继续遍历没有遍历的节点

所有我们需要记录节点是否遍历锅，

定义一个布尔类型的数组，记录所有节点的状态

将所有节点初始状态为False（因为初始的布尔数组都是False）

再遍历的过程中改为true

我们就知道状态为true的节点就是遍历过的节点

public static boolean[] isfStatus;

数据处理，深度搜索

理解遇到困难可以翻到该部分最下面，有示意图

1、启动，进入递归搜索

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

实现效果，处理内容

isfStatus = new boolean[dian_length];

初始化状态记录数组，长度为dian_length，状态为false

2、

for循环，判断节点是否遍历过（状态是否为false）

是，继续循环，判断下一节点

否：执行DFS操作，并向下搜索（深度搜索）

2、深度搜索，向下搜索遍历

  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. }

firstValue() 和 nextValue() 是两个自定义函数方法，对应代码在下面，可以先看下面理解，再来看这部分

简单来说，

firstValue() 是对节点对应的数组（二维数组对应 行）遍历的值

nextValue() 是对应的下一节点的值，将要遍历的下一节点

实现效果，处理内容

1、输出当前节点

2、将当前节点的状态改为true，标记为已经遍历过的节点

3、进入当前节点再二维数组里所对应的行，寻找下一级且没有遍历过的节点，进行DFS操作

!isfStatus[j] 如果不是isfStatus[]第j个数据，isfStatus[]是布尔类型数组，所有就是判断是否遍历

3、遍历原理，firstValue() 和 nextValue()的函数部分

  1.  
  2. /**                                           
  3.  * 第一个连接点                                     
  4.  * @param i                                   
  5.  * @return                                    
  6.  */                                           
  7. private static int firstValue(int i) {        
  8.     for (int j = 0; j < d_length; j++) {      
  9.         if (arr[i][j] > 0) {                  
  10.             return j;                         
  11.         }                                     
  12.     }                                         
  13.     return -1;                                
  14. }                                             
  15. /**                                           
  16.  * 下一个连接点                                     
  17.  * @param i                                   
  18.  * @param j                                   
  19.  * @return                                    
  20.  */                                           
  21. private static int nextValue(int i, int j) {  
  22.     for (int k = (j + 1); k < d_length; k++) {
  23.         if (arr[i][k] == 1) {                 
  24.             return k;                         
  25.         }                                     
  26.     }                                         
  27.     return -1;                                
  28. }    
  29. ————————————————
  30. 版权声明：本文为CSDN博主「红目香薰」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
  31. 原文链接：https://blog.csdn.net/feng8403000/article/details/128989010

4、结果输出

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

5、示意图，助消化

完整代码

//我写的注释和代码太乱了，还是复制原文了

//是大佬写的有点不好理解，上面是我的理解

  1.  
  2. public class Demo_def {
  3.     /**
  4.      * 顶点
  5.      */
  6.     public static String d[] = { "1", "2", "3", "4", "5", "6", "7" };
  7.     /**
  8.      * 图转换数组
  9.      */
  10.     public static int[][] arr= {
  11.             {0,1,1,0,0,0,0},
  12.             {1,0,0,1,1,0,0},
  13.             {1,0,0,0,0,1,0},
  14.             {0,1,0,0,0,0,1},
  15.             {0,1,0,0,0,0,0},
  16.             {0,0,1,0,0,0,0},
  17.             {0,0,0,1,0,0,0},
  18.     };
  19.     /**
  20.      * 顶点长度
  21.      */
  22.     public static int d_length=d.length;
  23.     /**
  24.      * 记录每一个节点的遍历过程，走过则记录为true
  25.      */
  26.     public static boolean[] isfStatus;
  27.     /**
  28.      * 开始递归
  29.      */
  30.     public static void DFSStart() {
  31.         //初始化数组，记录使用过程
  32.         isfStatus = new boolean[d_length];
  33.         //遍历图数组
  34.         for (int i = 0; i < d_length; i++) {
  35.             //因为初始的布尔数组都是false，所以只要是false就是没有走过
  36.             if (isfStatus[i] == false) {
  37.                 //进度到深度搜索的递归
  38.                 DFS(i);
  39.             }
  40.         }
  41.     }
  42.     /**
  43.      * 递归深搜
  44.      * @param i
  45.      */
  46.     private static void DFS(int i) {
  47.         // TODO Auto-generated method stub
  48.         System.out.print(d[i] + " ");
  49.         isfStatus[i] = true;
  50.         // 深度搜索子节点·从第一个节点到下一个节点
  51.         for (int j = firstValue(i); j >= 0; j = nextValue(i, j)) {
  52.             if (!isfStatus[j]) {
  53.                 DFS(j);
  54.             }
  55.         }
  56.     }
  57.     /**
  58.      * 第一个连接点
  59.      * @param i
  60.      * @return
  61.      */
  62.     private static int firstValue(int i) {
  63.         for (int j = 0; j < d_length; j++) {
  64.             if (arr[i][j] > 0) {
  65.                 return j;
  66.             }
  67.         }
  68.         return -1;
  69.     }
  70.     /**
  71.      * 下一个连接点
  72.      * @param i
  73.      * @param j
  74.      * @return
  75.      */
  76.     private static int nextValue(int i, int j) {
  77.         for (int k = (j + 1); k < d_length; k++) {
  78.             if (arr[i][k] == 1) {
  79.                 return k;
  80.             }
  81.         }
  82.         return -1;
  83.     }
  84.     public static void main(String[] args) {
  85.         // TODO Auto-generated method stub
  86.         DFSStart();
  87.     }
  88.  
  89. }
  90. ————————————————
  91. 版权声明：本文为CSDN博主「红目香薰」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
  92. 原文链接：https://blog.csdn.net/feng8403000/article/details/128989010
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/476110
推荐阅读
相关标签

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

  

闽ICP备14008679号