树的深度搜索遍历DFS

╰半夏微凉° 2022-12-11 07:54 176阅读 0赞

### 定义： ###

深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。

### 例题 ###

![在这里插入图片描述][e491e40bab50df0f671181969b24757b.png_pic_center]  
求图中的V0出发，是否存在一条路径长度为4的搜索路径。

分析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFoYTgxMjk_size_16_color_FFFFFF_t_70_pic_center]

伪代码：

/**
     * DFS核心伪代码
     * 前置条件是visit数组全部设置成false
     * @param n 当前开始搜索的节点
     * @param d 当前到达的深度，也即是路径长度
     * @return 是否有解
     */
    bool DFS(Node n, int d){
        
        if (d == 4){
        //路径长度为返回true，表示此次搜索有解
            return true;
        }
     
        for (Node nextNode in n){
        //遍历跟节点n相邻的节点nextNode，
            if (!visit[nextNode]){
        //未访问过的节点才能继续搜索
     
                //例如搜索到V1了，那么V1要设置成已访问
                visit[nextNode] = true;
     
                //接下来要从V1开始继续访问了，路径长度当然要加
     
                if (DFS(nextNode, d+1)){
        //如果搜索出有解
                    //例如到了V6，找到解了，你必须一层一层递归的告诉上层已经找到解
                    return true;
                }
     
                //重新设置成未访问，因为它有可能出现在下一次搜索的别的路径中
                visit[nextNode] = false;
     
            }
            //到这里，发现本次搜索还没找到解，那就要从当前节点的下一个节点开始搜索。
        }
        return false;//本次搜索无解
    }

DFS核心伪代码：

/**
     - DFS核心伪代码
     - 前置条件是visit数组全部设置成false
     - @param n 当前开始搜索的节点
     - @param d 当前到达的深度
     - @return 是否有解
     */
    bool DFS(Node n, int d){
        
        if (isEnd(n, d)){
        //一旦搜索深度到达一个结束状态，就返回true
            return true;
        }
     
        for (Node nextNode in n){
        //遍历n相邻的节点nextNode
            if (!visit[nextNode]){
        //
                visit[nextNode] = true;//在下一步搜索中，nextNode不能再次出现
                if (DFS(nextNode, d+1)){
        //如果搜索出有解
                    //做些其他事情，例如记录结果深度等
                    return true;
                }
     
                //重新设置成false，因为它有可能出现在下一次搜索的别的路径中
                visit[nextNode] = false;
            }
        }
        return false;//本次搜索无解
    }

注意：

*  遍历相邻节点的过程伪代码应该是没写出来，在写java代码的时候应该需要写出来。
 *  中间节点的nextNode有两个，要分两次判断
 *  visit数组中vo的值一开始就是true
 *  visit数组中为true的节点是指当前节点之前的节点
 *  visit数组中可以设置为true的节点只能是当前  
    节点
 *  isEnd（）方法判断是否走到头

[进阶传送门][Link 1]

[e491e40bab50df0f671181969b24757b.png_pic_center]: /images/20221123/7c3b5b936bc2408bba245cd6003a5fdb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFoYTgxMjk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0b4808734e3742c58f6717c08340151a.png
[Link 1]: https://www.cnblogs.com/DWVictor/p/10048554.html