前言:

前段时间复习了一下DFS，认为BFS不必多用，直到我认识到了BFS才具有最短性。

概述:

BFS最让我喜欢的一点是它有固定的模板，也就是套路。
先将初始点放进队列中，然后出列遍历每一个点，直到找到最优解，即为最短路。
模板如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
queue<int>q;
st[1]=true;
q.push(1)//从哪个点出发就先将该点放入队列中
while(q.size()){
    int t=q.front();
    q.pop();
    for(int i=h[t];i!=1;i=ne[i]){//bfs这个点的所有路径
        int j=e[i];
        if(!st[j]){
            st[j]=true;
            q.push(j);
        }
    }
}

实践

和讲解DFS一样都从走迷宫开始

题目:迷宫

这里就不继续写题目了，因为之前已经写过了，不了解的可以点击高亮的“迷宫”直接访问

1