广度优先搜索 (BFS)

理论

BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索．

是图上最基础、最重要的搜索算法之一．

所谓宽度优先．就是每次都尝试访问同一层的节点．如果同一层都访问完了，再访问下一层．

这样做的结果是，BFS 算法找到的路径是从起点开始的最短合法路径．换言之，这条路径所包含的边数最小．

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的．

实现

队列实现

BFS最常用的实现是依靠队列：使用队列存储待处理的点，每处理一个点就弹出该点，并将与该点相邻且未访问的点压入队列尾部。

双层bfs

通常用于需要计步的最短路，只适用于不带权的图。思路是使用嵌套whle循环层序遍历，在每一层开始用que.size()统计当前层的元素数量，并在内层while循环结束后增加计数。

参考代码

    que.push(0);
    isVis[0] = true;
    while (!que.empty()) {
        int sz = que.size();
        while (sz--) {
            int currU = que.front();
            que.pop();

            //此处处理搜索逻辑

            //将当前节点未被访问的出边压入队列
            for (int i : map[currU]) {
                if (isVis[i])continue;
                que.push(i);
                isVis[i] = true;
            }
        }
        res++;
    }

模板题

孤岛问题

计数

题目：99. 计数孤岛

点击展开题目

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例

输出示例

实现代码

点击展开代码

#include<iostream>
#include<queue>
#include<utility>
using namespace std;

//存图：二维表，元素为（类型，访问标记）构成的结构体
//遍历表，
//如果当前陆地未标记：计数器+1，访问该节点的所有相邻节点并标记陆地
//如果当前陆地未标记：跳过

//bfs逻辑：
//从左到右从上到下遍历所有地块，如果查找到没有标记的陆地则以当前陆地为起点进行bfs，标记所有相邻陆地为已访问，并计数器+1

const int MAX=55;
int n,m;
int sum=0;
queue<pair<int,int>> curr;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

struct point{
    bool isvist=false;
    int island=0;
}map[MAX][MAX];


int main(){
    cin>>n>>m;
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            cin>>map[x][y].island;
        }
    }

    //遍历地图
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            if(map[x][y].island==0)continue;
            if(map[x][y].isvist)continue;

            //发现wei'fang
            //注意入队后及时标记访问
            sum++;
            map[x][y].isvist=true;
            curr.push({x,y});
            while(!curr.empty()){
                    pair<int,int> currP=curr.front();
                    curr.pop();
                for(int i=0;i<4;i++){
                    int a=currP.first+dx[i];
                    int b=currP.second+dy[i];
                    if(a>n||a<1||b>m||b<1)continue;
                    if(map[a][b].isvist)continue;
                    if(map[a][b].island==0)continue;

                    curr.push({a,b});
                    map[a][b].isvist=true;
                }
            }
        }
    }

    cout<<sum;

    return 0;
}

单源最短路

题目：码蹄集OJ-都市路径

思路

带计数的单源最短路，在双层BFS的基础上将访问标记数组更换为一个记录最短步数的数组，初始化为-1表示没有访问。

需要注意起点的步数始终为0。

实现代码

点击展开代码

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

const int MAX = 105;
int n,u,k,v,path=0;
vector<int> map[MAX];
queue<int> que;
int vis[MAX];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> u >> k;
        for (int j = 0; j < k; j++) {
            cin >> v;
            map[u].push_back(v);
        }
    }

    //初始化vis数组
    for (int i = 1; i <= n; i++) {
        vis[i] = -1;
    }

    //查图
    que.push(1);
    vis[1] = 0;
    while (!que.empty()) {
        int sz = que.size();
        path++;
        while (sz--) {
            int curr = que.front();
            que.pop();

            for (int i : map[curr]) {
                if (vis[i] == -1) {
                    que.push(i);
                    vis[i] = path;
                }
            }
        }
    }

    //输出
    for (int i = 1; i <= n; i++) {
        if (i != 1)cout << endl;
        cout << i << " " << vis[i];
    }

    return 0;
}

带移动规则的单源最短路

题目：码蹄集OJ-马走日

思路

需要确定一点：尽管题目为多次询问，但本质上仍然只有一个起点。为了简化计算，可以在确定地图范围和起点后进行一次全局的BFS并存储抵达每个点时的结果，在后续询问中直接查询输出即可。

对于特殊的移动规则，修改dx和dy符合规则即可。

实现代码

点击展开代码

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
//带特殊移动规则的单源最短路，bfs
//剪枝 ？ 先询问方向，分为上下左右   先算出来再考虑

const int MAX = 505;
int n, a, b, targetA, targetB,num;
bool isDiv = false;
int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
int dest[MAX][MAX];
queue<pair<int, int>> que;

void print(int i,int str) {
    if (i != 0)cout << "\n";
    cout << str;
}

int main() {
    cin >> n >> a >> b >> num;

    //初始化所有点距离当前所在位置的距离为-1
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dest[i][j] = -1;
        }
    }

    //从当前点开始bfs，检查到每个点的最短路
    que.push({ a,b });
    dest[a][b] = 0;
    int des = 0;

    while (!que.empty()) {
        int sz = que.size();
        des++;
        while (sz--) {
            pair<int, int > curr= que.front();
            que.pop();

            for (int i = 0; i < 8; i++) {
                pair<int, int> next = { curr.first + dx[i],curr.second + dy[i] };
                if (next.first<0 || next.first>n || next.second<0 || next.second>n)continue;
                if (dest[next.first][next.second] != -1)continue;

                dest[next.first][next.second] = des;
                que.push(next);
            }
        }
    }


    //接收询问并查找输出
    for (int i = 0; i < num; i++) {
        cin >> targetA >> targetB;
        print(i, dest[targetA][targetB]);
    }

    return 0;
}

多源最短路

题目：码蹄集OJ-小码哥的01点阵

思路

多源最短路问题，需要注意转换思路为从单个点逐一搜索转换为多个起点直接放进初始队列同时搜索。

在本题中，从所有0点开始向外搜索并标记，每遇到一个未访问的非0点，当前向外扩散的层数就是该点最近的0点的距离。在搜索上，和常规的双层while循环bfs没有区别。

实现代码

点击展开代码

#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<cmath>
using namespace std;

const int MAX = 105;
int n, m,des;
string temp;

queue<pair<int, int>> que;
bool isVis[MAX][MAX];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };

struct Point {
    bool sig;
    int des;
}map[MAX][MAX];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        for (int j = 0; j < m; j++) {
            if (temp[j] == '0') {
                map[i][j].sig = false;
                map[i][j].des = 0;
                que.push({ i,j });
            }
            else map[i][j].sig = true;
        }
    }

    des = 0;
    //将所有为0的点放入初始队列进行bfs
    while (!que.empty() ){
        int sz = que.size();
        des++;
        while (sz--) {
            pair<int, int> curr = que.front();
            que.pop();

            //向四个方向扩散，如果是未经访问的非0点则记录距离并入队
            for (int i = 0; i < 4; i++) {
                if (curr.first + dx[i] < 0 || curr.first + dx[i] >= n || curr.second + dy[i] < 0 || curr.second + dy[i] >= m)continue;
                if (!map[curr.first + dx[i]][curr.second + dy[i]].sig)continue;
                if (isVis[curr.first + dx[i]][curr.second + dy[i]])continue;

                isVis[curr.first + dx[i]][curr.second + dy[i]] = true;
                map[curr.first + dx[i]][curr.second + dy[i]].des = des;
                que.push({ curr.first + dx[i],curr.second + dy[i] });
            }
        }
    }

    //遍历并输出
    for (int i = 0; i < n; i++) {
        if (i != 0)cout << endl;
        for (int j = 0; j < m; j++) {
            if (j != 0)cout << " ";
            cout << map[i][j].des;
        }
    }

    return 0;
}

单词接龙

题目：110. 字符串迁移

点击展开题目

# 题目描述

字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列：

序列中第一个字符串是 beginStr。
序列中最后一个字符串是 endStr。
每次转换只能改变一个字符。
转换过程中的中间字符串必须是字典 strList 中的字符串，且strList里的每个字符串只用使用一次。

给你两个字符串 beginStr 和 endStr 和一个字典 strList，找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列，返回 0。

# 输入描述

第一行包含一个整数 N，表示字典 strList 中的字符串数量。第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。后续 N 行，每行一个字符串，代表 strList 中的字符串。

# 输出描述

输出一个整数，代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列，则输出 0。

# 输入示例

6
abc def
efc
dbc
ebc
dec
dfc
yhn

# 输出示例

# 提示信息

从 startStr 到 endStr，在 strList 中最短的路径为 abc -> dbc -> dec -> def，所以输出结果为 4，如图：

数据范围：

2 <= N <= 500

思路

该类型题目的关键在于人为构造图，其后使用bfs进行搜索即可。

实现代码

点击展开代码

## include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int MAX = 510;
int n, res,len;
string beginStr, endStr,temp;
bool isVis[MAX], isRes;
string strDic[MAX];
vector<int> map[MAX];
queue<int> que;

void checkStr(int x,int y) {
    int diff = 0;
    for (int i = 0; i < len; i++) {
        if (strDic[x][i] != strDic[y][i])diff++;
        if (diff > 1)break;
    }
    if (diff == 1) {
        map[x].push_back(y);
        map[y].push_back(x);
    }
}

int main() {
    cin >> n;
    cin >> beginStr >> endStr;
    strDic[0] = beginStr;
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        strDic[i]=temp;
    }
    strDic[n + 1] = endStr;
    len = beginStr.size();

    //预处理建图
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= n + 1; j++) {
            checkStr(i, j);
        }
    }

    //查图
    que.push(0);
    isVis[0] = true;
    while (!que.empty()) {
        int sz = que.size();
        while (sz--) {
            int currU = que.front();
            que.pop();

            if (currU == n + 1) {
                isRes = true;
                while (!que.empty())que.pop();
                break;
            }

            for (int i : map[currU]) {
                if (isVis[i])continue;
                que.push(i);
                isVis[i] = true;
            }
        }
        res++;
    }

    if (isRes)cout << res;
    else cout << 0;



    return 0;
}

广度优先搜索 (BFS)

理论

实现

队列实现

双层bfs

模板题

孤岛问题

计数

题目描述

输入描述

输出描述

输入示例

输出示例

实现代码

单源最短路

思路

实现代码

带移动规则的单源最短路

思路

实现代码

多源最短路

思路

实现代码

单词接龙

# 题目描述

# 输入描述

# 输出描述

# 输入示例

# 输出示例

# 提示信息

思路

实现代码

其它题目记录