BFS Introduction

宽度优先搜索（BFS，Breadth-First Search）与深度优先搜索类似，从某个状态出发搜索所有可以到达的状态。

与深度优先搜索的不同之处在于搜索的顺序，宽度优先搜索总是先搜索距离初始状态近的状态。也就是说，它是按照开始状态 -> 只需一次转移就可以达到的所有状态 -> 只需两次转移就可以达到的所有状态 -> … … 这样的顺序进行搜索。对于同一个状态，宽度搜索只经过一次，因此复杂度为 O(状态数 * 转移方式)。

深度优先搜索（隐式地）利用了栈进行计算，而宽度优先搜索则利用了队列。搜索时首先将初始状态添加到队列里，此后从队列的最前端不断取出状态，把从该状态可以转移到的状态中尚未访问过的部分加入队列，如此往复，直至队列被取空或找到问题的解。

Question

question

Analysis

宽度优先搜索按照距开始状态由近及远的顺序进行搜索，因此可以很容易地用来求最短路径、最少操作之类的问题的答案。这个问题中状态只是目前的位置坐标，因此可以构造成 pair 或者编码成 int 来表达状态，当状况更加复杂时就需要封装成一个类来表示状态了。

Solution

//
//  bfs.cpp
//  BFS
//
//  Created by dusign on 2019/10/31.
//  Copyright © 2019 gang du. All rights reserved.
//

#include <iostream>
#include <queue>

using namespace std;

// 尚未达到的距离，无穷大
const int INF = 100000000;
const int MAX_N = 100;
const int MAX_M = 100;

typedef pair<int, int> P;

char maze[MAX_N][MAX_M + 1];
int N, M;
int sx, sy;
int gx, gy;

int d[MAX_N][MAX_M];

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int bfs(){
    queue<P> que;
    
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            d[i][j] = INF;
    
    que.push(P(sx, sy));
    d[sx][sy] = 0;
    
    while(que.size()){
        P p = que.front();
        que.pop();
        
        if(p.first == gx && p.second == gy) break;
        
        for(int i = 0; i < 4; i++){
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];
            
            if(0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF){
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }
    
    return d[gx][gy];
}


void solve(){
    int res = bfs();
    cout << res <<endl;
}


int main(){
    cin >> N >> M;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++){
            cin >> maze[i][j];
            if(maze[i][j] == 'S'){
                sx = i;
                sy = j;
            }
            if(maze[i][j] == 'G'){
                gx = i;
                gy = j;
            }
        }
    
    solve();
    return 0;
}

Remark

宽度优先搜索会把状态逐个加入队列，因此通常需要与状态数成正比的内存空间。而深度优先搜索是与最大的递归深度成正比。一般与状态数相比，递归的深度并不会太大，所以可以认为深度优先搜索更加节省内存。

此外，也有采用与宽度优先搜索类似的状态转移顺序，并注重节约内存占用的迭代加深深度优先搜索（IDDFS, Iterative Deepening Depth-First Search）。IDDFS 是一种在最开始将深度优先搜索的递归次数限制在1次，在找到解之前不断增加递归深度的方法。

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

...

00:00

Breadth-first search is one of the most commonly used algorithms.

Question

Analysis

Solution

Remark

...

FEATURED TAGS

FRIENDS