C++U5-第04课-广度优先搜索1

学习目标

广度优先搜索简称广搜搜，英文缩写（BFS）
顾名思义就是按照广度顺序优先进行枚举，其本质也是一种暴力枚举的思想。

广度优先搜索（Breadth-First Search，简称BFS）是一种图搜索算法，用于遍历或搜索图数据结构的所有节点。该算法从起始节点开始，逐层地向外扩展，先访问当前节点的所有邻居节点，然后再逐层访问邻居的邻居，以此类推。BFS通常使用队列数据结构来实现，确保先访问到达的节点。

这一算法最早应用于解决迷宫问题，但后来发展成一种在图和树等数据结构中广泛应用的搜索和遍历方法。BFS在找寻最短路径、图的连通性检测、网络分析等领域都有重要的应用。

以下是广度优先搜索算法的一些主要特点和应用背景：

1. 最短路径问题： BFS可以用于寻找两个节点之间的最短路径。在无权图中，BFS能够找到起点到终点的最短路径。

2. 连通性检测： BFS可用于确定图是否是连通的，即是否存在一条路径能够连接图中的所有节点。

3. 状态空间搜索： 在人工智能领域，BFS被广泛用于搜索状态空间，特别是在解决问题的状态图中寻找解决方案的过程中。

4. 网络分析： 在社交网络、网络通信等领域，BFS用于发现节点之间的关系、寻找影响力最大的节点等分析任务。

总的来说，广度优先搜索算法在解决图论和网络相关问题时具有广泛的应用，是一种基础且有效的算法。

课程引例 

 广搜

[【广度优先搜索(一)】抓住那头牛]

【题目分析】
【题意分析】
通过 X−1 和 X+1 和 2×X 的方式，农夫如何花费最短的时间抓住牛

【思路分析】
由于位置的个数很少且要求最小步数，可以考虑从 n 位置开始广搜，同时用一个数组 d，d 
i
​
  表示从 n 位置到 i 位置需要的步数，用队列的方式，首先将初始位置压入队列。当队列不为空时，取出队列头并丢掉，将队列头能到达的位置重新压入队列。当取出的位置为k时候最后输出到达k位置的时间。

【参考代码】
#include <bits/stdc++.h>
using namespace std;
int d[100009];
int main() {
    int n, k;
    cin >> n >> k;
    // 首先先将所有的点初始化为-1，不可到达的情况
    for (int i = 1; i <= 100000; i++) {
        d[i] = -1;
    }
    // 当前位置初始化为0
    d[n] = 0;
    // 创建队列并且将当前初始的位置压入队列
    queue<int> q;
    q.push(n);
    while (q.size()) {
        // 取出队头的位置
        int r = q.front();
        q.pop();
        // 已经到达点k位置，那么输出到达点k的最小的步数
        if (r == k) {
            cout << d[k];
            break;
        }
        // 枚举三个操作:当前位置-1、当前位置+1、当前位置*2
        // 当前位置-1不小于0，并且该位置未到达过，那么将当前压入队列
        if (r >= 1 && d[r - 1] == -1) {
            d[r - 1] = d[r] + 1;
            q.push(r - 1);
        }
        // 当前位置+1不大于100000，并且该位置未到达过，那么将当前压入队列
        if (r <= 100000 && d[r + 1] == -1) {
            d[r + 1] = d[r] + 1;
            q.push(r + 1);
        }
        // 当前位置*2不大于100000，并且该位置未到达过，那么将当前压入队列
        if (2 * r <= 100000 && d[2 * r] == -1) {
            d[2 * r] = d[r] + 1;
            q.push(2 * r);
        }
    }
    return 0;
}

[【广度优先搜索(一)】迷宫]

【题意分析】
# 的位置不能行走，从起点可以走到终点最少需要多少步。

【思路分析】
我们将当前的坐标和步数储存在结构体内，用队列的方式，首先先将开始的位置压入队列中，然后while循环判断队列不为空，取出队列队首，然后遍历取出元素的四个方向，然后当前方向可以行走，那么将可以行走的位置再压入队列。直到找到终点，输出步数，退出循环

【参考代码】
#include <bits/stdc++.h>
using namespace std;
// 定义地图数组和标记数组标记当前位置是否走过
char MAP[49][49];
bool vis[49][49];
struct node {
    int x, y, step;
} l, r;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> MAP[i][j];
        }
    }
    // 定义队列将初始位置压入，起点1,1步数0,并且标记起点已经走过
    queue<node> q;
    q.push({1, 1, 0});
    vis[1][1] = 1;
    while (q.size()) {
        // 取出当前的队头并且丢掉
        r = q.front();
        q.pop();
        // 如果取出的队头刚好是终点，那么输出步数，退出while循环
        if (r.x == n && r.y == m) {
            cout << r.step;
            break;
        }
        // 遍历当前队头的四个方向
        for (int i = 0; i < 4; i++) {
            // 计算下一步位置的坐标，并且将步数+1
            l.x = r.x + dir[i][0];
            l.y = r.y + dir[i][1];
            l.step = r.step + 1;
            // 如果下一步位置并未超出边界并且下一步的位置并未走过，而且地图上为可行走的.
            if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= m && !vis[l.x][l.y] && MAP[l.x][l.y] == '.') {
                // 将下一步位置标记走过并且将下一步位置压入队列
                vis[l.x][l.y] = 1;
                q.push(l);
            }
        }
    }
    return 0;
}

总结

信息编码

本节课作业分析：

正在整理中，稍等······