Acwing BFS

一般通过队列实现，当边的权值相同时具有最短性，可以求最少操作步数。相比DFS无需回溯，而是逐层搜索。

Acwing 844 走迷宫

输入样例：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

8

思路分析：广度优先搜索

• 设置一个二维数组g[][]存储图，设置一个队列q[]（pair<int,int>类型的，每个值存储坐标(x,y))，表示当前到达的坐标位置，设置一个距离数组d[][],d[x][y]表示到原点的距离
• 当队列不为空时，取出队头元素，像四个方位进行判断，看是否可走，可走的路径更新距离，坐标存入数组；
• • 关于方位的选择，为简化代码，不用写四行判断来检验每个方位。设置两个一维数组dx[4]={0,1,0,-1},dy = {1,0,-1,0},然后循环四次，每次坐标加上对应的dx、dy，判断当前位置是否可走，若可走就更新坐标到原点的距离d[x][y]+1,并将新坐标加入队列；

具体实现代码（详解版）：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
typedef pair<int,int> PII;
int n,m;
int g[N][N],d[N][N];//存图和距离
PII q[N * N];//数组模拟队列

int bfs(){
    memset(d,-1,sizeof d);//初始化距离为-1 表示当前坐标未走过
    d[0][0] = 0;
    
    q[0]={0,0};//队列初始化
    int hh = 0,tt = 0;//队头，队尾
    
    int dx[4] = {0,1,0,-1},dy[4]={-1,0,1,0};//上下左右四个方向
    while(hh <= tt){//队列不为空
       auto t = q[hh ++];//取出队头元素
       
       for(int i = 0; i < 4 ;i ++){//四个方位循环判断哪条可走
           int  x = t.first + dx[i],y = t.second + dy[i];//得到新坐标
           if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y]  == -1){//这个坐标可以走
               d[x][y] = d[t.first][t.second] + 1;//更新距离加1
               q[++tt] = {x,y};//当前坐标入队
           }
           
       }
        
    }
    return d[n-1][m-1];
}

int main(){
    cin >> n >> m;
    for(int i = 0 ; i < n; i ++){
        for(int j = 0 ; j < m ;j ++){
            cin >> g[i][j];
        }
    }
    cout << bfs() << endl;
}

若想要存储经过的路径，可以设置一个p[][]（PII)，p[x][y]存储当前位置坐标的前驱坐标，判断好要走的方位时，更新，然后从(n-1,m-1)开始遍历输出，即为从终点到原点经过的坐标

II p[N][N];
if(x>=0 && y>=0 && x<n && y<m && g[x][y]==0 && d[x][y]==-1){
                d[x][y]=d[t.first][t.second]+1;
                q[tt++]={x,y};
    p[x][y]=t;//记录当前坐标的前驱坐标 即从哪个点过来的
            }
//输出
int x=n-1,y=m-1;//终点到原点的路径输出
while(x || y){
    cout<<x<<","<<y<<endl;
    auto t=p[x][y];//得到前驱
    x=t.first,y=t.second;
}

Acwing 845 .八数码问题

实现思路：

• 首先题意：
• 可以转化为求图的最短距离，且权值为1，使用BFS；
• 怎么表示状态（即每次移动后的矩阵是怎样的）：
• • 将3*3的矩阵按顺序转化为字符串，即s=“123x46758”;
• • BFS要使用队列，这时候队列就存储字符串queue<string>
• 如何记录到达每一个状态时移动的距离：使用一个字典,使用一个字典，字符串状态与已经移动的距离相对应，即unordered_map<string,int>
• 然后按照BFS的步骤进行
• • 初始状态入队列，并且使用哈希表 unordered_map 来记录每个状态的步数。
• • 每次从队列中取出当前状态，检查是否是目标状态。如果是，则返回步数。
• • 否则，将当前状态的空格 x 移动到四个方向之一（上下左右），生成新的状态。
• • 如果新状态未出现过，记录该状态并将其入队，继续下一轮搜索
• 初始状态是通过输入的字符串形成的 start，目标状态是固定的 end = “12345678x”。每次从队列中取出当前状态，找到空格 x的位置，然后尝试将空格与相邻的数字交换，并生成新的状态。记录新状态的步数，如果达到目标状态则返回结果。

注意：

• 字符串下标k---->矩阵位置(x,y)：x=k/3,y=k%3；
• 矩阵位置(x,y)---->字符串下标k：k=x*3+y

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

int bfs(string start) {
    // 定义目标状态
    string end = "12345678x";
    
    // 定义字符串队列
    queue<string> q;
    q.push(start);  // 初始状态入队
    
    // 定义距离哈希表，记录每个状态的步数
    unordered_map<string, int> d;
    d[start] = 0;  // 初始状态的步数为 0
    
    // 四个方向的移动偏移
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    // BFS 遍历
    while (q.size()) {
        auto t = q.front();  // 取出队头元素
        q.pop();
        int dist = d[t];  // 得到当前状态的步数
        
        // 如果当前状态已经是目标状态，返回步数
        if (t == end) return dist;
        
        // 找到 'x' 的位置
        int k = t.find('x');
        int x = k / 3, y = k % 3;  // 将一维索引转换为二维坐标
        
        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            
            // 检查新的坐标是否在有效范围内
            if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                swap(t[k], t[a * 3 + b]);  // 交换 'x' 和相邻位置的数
                
                // 如果新状态没有被访问过，将其入队并记录步数
                if (!d.count(t)) {
                    d[t] = dist + 1;
                    q.push(t);
                }
                
                // 还原状态，为下一个方向的移动做准备
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    
    return -1;  // 如果不能到达目标状态，返回 -1
}

int main() {
    string start;
    
    // 输入初始状态的 9 个字符
    for (int i = 0; i < 9; i++) {
        char c;
        cin >> c;
        start += c;
    }
    
    // 输出最少的移动次数
    cout << bfs(start) << endl;
}

BFS（广度优先搜索）总结

广度优先搜索（BFS）是一种图遍历算法，适用于求解最短路径、连通性、搜索层次结构等问题。它从起始点开始，逐层遍历每一层的所有相邻节点，直到找到目标节点或遍历完整个图。BFS是无权图中计算最短路径的有效方法。广度优先搜索是一种高效且简单的图遍历算法，适用于求解无权图中的最短路径问题。通过使用队列，BFS能够按层次遍历图中的节点，保证最短路径的求解。在实际问题中，如迷宫、拼图、连通性检查等，BFS是常用的算法之一。

DFS与BFS的对比理解
BFS（广度优先搜索）和 DFS（深度优先搜索）是两种经典的图遍历算法，它们在遍历顺序、应用场景、实现方式和性能上都有显著的不同。下面将从多个角度对这两种算法进行详细对比。

• 遍历顺序
• • BFS（广度优先搜索）：从起点出发，优先遍历距离起点最近的节点，逐层扩展，直到遍历完所有节点或者找到目标节点。BFS通常用于按层次遍历节点；
• • DFS（深度优先搜索）：从起点出发，一直深入到某条路径的尽头，直到无法继续为止，再回溯到上一个分支点并继续探索其他路径。DFS是先走“深”的节点，后处理“宽”的节点；
• 搜索路径和解的性质
• • BFS：适合用于寻找无权图中的最短路径，因为BFS按照层次逐层扩展，首先到达某个节点的路径一定是最短路径。它遍历到某一层时，会访问到该层所有的节点；
• • DFS：适合用于寻找所有解或者进行路径探索，但它不保证找到的是最短路径。如果问题需要找到全部解或者对图中的某些部分进行深度探索，DFS更有效；
• 数据结构
• • BFS：依赖于队列，队列保证了先入先出的顺序，确保节点是按层次遍历的。新发现的节点会在队列的末尾等待被访问；
• • DFS：依赖于栈，可以用递归或者显式栈来实现。DFS通过栈的后入先出性质，能够优先深入到图的最深处；
    
    以上就是BFS的一些知识和练习，注意与DFS进行对比学习~

原文地址：https://blog.csdn.net/qq_43060884/article/details/142433278

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！