java--DFS深度搜索方法

怼烎@ 2024-03-27 16:12 44阅读 0赞

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

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

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

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

深度搜索就是：

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

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

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

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

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

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

![af5c130f7fc0e5a7237feaac5d300a49.png][]

![de59d43236dcedefb83605c3c740d7bc.jpeg][]

## 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的二维数组

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},
        };

好像没有关系，其实很容易理解

![4bd51b2e36fe86501a14c51f34b17709.jpeg][]

#### 4、布尔数组，是否遍历的记录 ####

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

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

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

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

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

再遍历的过程中改为true

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

public static boolean[] isfStatus;

### 数据处理，深度搜索 ###

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

#### 1、启动，进入递归搜索 ####

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

**实现效果，处理内容**

isfStatus = new boolean\[dian\_length\];

初始化状态记录数组，长度为dian\_length，状态为false

2、

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

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

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

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

/**                                                       
     * 递归深搜                                                   
     * @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);                                       
            }                                                 
        }                                                     
    }

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

简单来说，

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

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

**实现效果，处理内容**

1、输出当前节点

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

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

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

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

/**                                           
     * 第一个连接点                                     
     * @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;                                
    }    
    ————————————————
    版权声明：本文为CSDN博主「红目香薰」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
    原文链接：https://blog.csdn.net/feng8403000/article/details/128989010

#### 4、结果输出 ####

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

#### 5、示意图，助消化 ####

![f014f62e0036012a3301f6d93e10a769.jpeg][]

![51e6060bd5b05edd2e24bc67eb6766b1.jpeg][]

## 完整代码 ##

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

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

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();
        }
     
    }
    ————————————————
    版权声明：本文为CSDN博主「红目香薰」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
    原文链接：https://blog.csdn.net/feng8403000/article/details/128989010

[5_ DFS_JAVA_-CSDN]: https://blog.csdn.net/feng8403000/article/details/128989010
[af5c130f7fc0e5a7237feaac5d300a49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/cba603be412c47dbad95b6947de0b8f1.png
[de59d43236dcedefb83605c3c740d7bc.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9ed8352e939c42d083c7d646efd5ec2a.png
[4bd51b2e36fe86501a14c51f34b17709.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/47f2d326cbc947d9abb1289375125ee1.png
[f014f62e0036012a3301f6d93e10a769.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1b4e8d43ecc140da84c74cd3eeccf204.png
[51e6060bd5b05edd2e24bc67eb6766b1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1d0c7cd895604c2fbb500f903befeebb.png