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

1. DFS（深度优先遍历）

理论介绍

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

博主个人理解

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

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

他的遍历是将每一种可能走到头，然后回溯的，这也是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;//恢复现场
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

2.BFS（宽度优先遍历）

理论介绍

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

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

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

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

代码实现

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

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