[编程笔记]-BFS广度优先搜索

前言

BFS(Breadth First Search)，广度优先搜索，典中典，重中重。

作用

一般用来在图、树中进行搜索。

原理

过程可视作一棵树，每次把所有子节点都搜一遍，然后把所有子节点加入待搜索的队列中，排着队一个一个搜，每一个又把所有子节点加入队中……

其实就是一层一层地搜索~

实现

一般用队列来模拟，需要O(2^h)的空间。同时，由于BFS算法的性质，它可以用来解决“最短路”问题。

实现最短路：第一次搜到的点肯定是离根节点最近的路径搜到的点。

代码

本来不想写的，但是想到DFS那里我就鸽了所以这里不得不写了hh

void bfs(int be, int en){
	int d[N];queue<int> q;
	memset(d,-1,sizeof(d));
	d[be]=0;q.push(d);
	while(!q.empty()){
		//取出点
		//找相邻点
		//如果是终点就直接退出了。
	}
}

为啥不打完呢……因为BFS的写法很多样，不唯一，所以给个思路就行了。

（归根结底就是这个蒟蒻太懒了hhh）

例题

就来一道毒瘤吧

AcWing845-八数码

#include<bits/stdc++.h>
using namespace std;

char a;
string str="";
string en="12345678x";

unordered_map<string,int> d;

void bfs(string be){
    queue<string> q;
    q.push(be);
    d[be]=0;
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    while(!q.empty()){
        string now=q.front(),tstr;q.pop();
        if(now==en)return;
        int t=now.find('x');
        int tx=t/3,ty=t%3;
        for(int i=0;i<4;i++){
            int nx=tx+dx[i],ny=ty+dy[i];
            if(0<=nx&&nx<3&&0<=ny&&ny<3){
                tstr=now;
                swap(tstr[t],tstr[nx*3+ny]);
                if(!d.count(tstr)){
                    d[tstr]=d[now]+1;
                    q.push(tstr);
                }
            }
        }
    }
}

int main(){
    cin.tie(0);cout.tie(0);
    for(int i=1;i<=9;i++){
        cin>>a;
        str+=a;
    }
    bfs(str);
    if(!d.count(en))cout<<-1;
    else cout<<d[en];
    return 0;
}

完结撒花o(￣︶￣)o