【蓝桥杯训练】DFS与BFS讲解

小咪咪 2024-03-25 14:04 72阅读 0赞

#### 1. DFS（深度优先遍历） ####

**理论介绍**

DFS属于图算法的一种，是针对图和树的遍历算法。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆或栈来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，如果遇到死路就往回退，回退过程中如果遇到没探索过的支路，就进入该支路继续深入，每个节点只能访问一次。

**博主个人理解**

DFS（深度优先遍历），是图论中的一种遍历方式，我们可以认为DFS是一个执着的人，不到南墙不回头，他会一直走到头，然后回溯，空讲比较抽象，我们直接来看DFS的一个应用，排列数字，如这样一个例题

![image-20230314213628492][]

那么他是怎样去遍历呢？ 以n=3为例，从根节点开始，第一层有三种选择方式分别是1，2，3，那么对应第二层就有2，3 或者1，3或者1，2这几种选择，可以看下面这张图

![image-20230314213905982][]

![image-20230314214024000][]

他的遍历是将每一种可能走到头，然后回溯的，这也是DFS的标志，执着！

**代码实现**

import java.util.*;
    public class Main{
        
        static int N = 10,n;
        static int[] path = new int[N];//记录路径
        static boolean st[] = new boolean[N];//记录数字是否已被使用
        
        public static void main(String[] args){
        
            Scanner scan = new Scanner(System.in);
            n = scan.nextInt();
            dfs(0);//从第0层开始遍历
        }
        
        public static void dfs(int u){
        
            if(u == n){
        //遍历至最后一层
                for(int i = 0;i<n;i++) {
        
                    System.out.print(path[i]+" ");//输出结果之一
                }
                System.out.println();
                    return;//结束，并回溯
            }
            for(int i = 1;i<=n;i++){
        
                if(!st[i]){
        //当前数字未被使用过
                    path[u]=i;//记录当前这一层的数字
                    st[i]=true;//将这个数字表示已使用过，这样接下来就不会再被使用
                    dfs(u+1);//遍历下一层
                    st[i]=false;//恢复现场
                }
            }
        }
    }

主要解题思路，从0层开始以dfs的方式去遍历，如果判断到了最后一层则回溯，在每一层判断时，先枚举数字是否被使用过，如果未被使用过，则将其记为本层使用的数字，并标记使用过了，同时遍历下一层，注意要恢复现场，否则会对其余遍历造成影响。

#### 2.BFS（宽度优先遍历） ####

**理论介绍**

广度优先搜索（也称宽度优先搜索）是连通图的一种遍历算法，也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和广度优先搜索类似的思想。属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。  
**博主个人理解**

BFS是比较贪心且懒惰的一个人，他会优先去搜索自己周围**最近**的**所有**单位，直到最近的都被找过了，去找下一接近的，直至最后，也因为他的懒惰，所以这种算法使用于最短路径问题！还是直接来例题 走迷宫  
![在这里插入图片描述][869e81c5b63c4fe881481df4ee26fe72.png]

读题可知，要求的是所有出路中最短的那一条，这正是BFS的适用解，我们看一下遍历过程

![image-20230314215353061][]

要注意的是 每次拓展的是，能在规定步数内走到的所有点位！

**代码实现**

import java.io.*;
    public class Main{
        
        static int N = 110;
        static int hh,tt,n,m;
        static int[][] g = new int[N][N];//用来存储迷宫地图
        static int[][] d = new int[N][N];//用来存储走的距离
        static PII[] q = new PII[N*N];//用来放每个点的下标
        public static int bfs(){
        
            hh = 0;tt = -1;
            d[0][0] = 0;//左上角，因为是起点，初始化为0
            q[++tt] = new PII(0,0);
            int[] dx = {
        -1,0,1,0};//上(-1,0) 下(1,0)
            int[] dy = {
        0,1,0,-1};//左(0,-1) 右(0,1)，这里是图论中常用的坐标移动方法
            while(hh<=tt){
        //队列不空，说明还没有遍历过所有点
                PII t = q[hh++];//取出队头
                for(int i = 0;i < 4;i++){
        
                    int x = t.first+dx[i];
                    int y = t.second+dy[i];//这里是遍历四个方位
                    if(x>=0 && x<n && y>=0 && y<m && d[x][y]==-1 && g[x][y]!=1){
        
          //解释下条件     x移动后没有越界    y移动后没有越界  当前点位还没来过  这个点是通的，-1表示此路不通
                        d[x][y]=d[t.first][t.second]+1;
                        q[++tt] = new PII(x,y);//移动后的点符合最近且为遍历过，且不越界的条件，入队！
                    }
                }
            }
            return d[n-1][m-1];
        }
        public static void main(String[] args)throws IOException{
        
            BufferedReader re = new BufferedReader(new InputStreamReader(System.in));//快读
            BufferedWriter wt = new BufferedWriter(new OutputStreamWriter(System.out));//快写
            String[] s = re.readLine().split(" ");
            n = Integer.parseInt(s[0]);
            m = Integer.parseInt(s[1]);
            for(int i = 0 ; i < n ;  i ++ ){
        
                String[] st = re.readLine().split(" ");
                for(int j = 0 ; j < m ;j ++ ){
        
                    g[i][j] = Integer.parseInt(st[j]);//读入迷宫地图
                    d[i][j] = -1;//将所有距离设为-1
                }
            }
            System.out.println(bfs());
            wt.close();
        }
    }
    class PII{
        //存储结构，就是存的坐标，因为要存在队列里，所以不能直接写，要包装以下
        int first,second;
        public PII(int first,int second){
        
            this.first  = first;
            this.second = second;
        }
    }

主要解题思路，以bfs的方式遍历整个地图，用d数组来记录走了多远，那么d\[n\]\[m\]就是最短距离，先遍历起点，然后按照其可以移动的位置，将所有可能存入队列中，遍历队列里的每一个点，并继续添加，直至所有点都被遍历完成，这样得出最后的答案。

[image-20230314213628492]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b5c366c2f29c47b48cc59a60e4bb3d1e.png
[image-20230314213905982]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8b18116c920543b78cc5189926324115.png
[image-20230314214024000]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/11a8ffc0a47d4ba6b129886f0e8dd4e4.png
[869e81c5b63c4fe881481df4ee26fe72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ebea441738bf4dd6a824d55634ba941b.png
[image-20230314215353061]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/be790078ad8d480b838ec5a826b483a1.png