bfs 订阅
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。 展开全文
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
信息
外文名
BFS
别    称
广度优先搜索
应用学科
计算机
中文名
宽度优先搜索算法
适用领域范围
计算机算法
宽度优先搜索概述
BFS,其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如队列或是链表),而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed表)
收起全文
精华内容
下载资源
问答
  • BFS

    千次阅读 2018-12-07 23:44:12
    BFS
    //给一个地图由起点到点最短步数 .通*不通
    //标准广搜模版题
    #include<bits/stdc++.h>
    using namespace std;
    char mp[103][103];          //地图大小
    int vis[103][103];          //访问标记
    typedef struct point pt;    //点重命名
    struct point{int x;int y;}; //点结构体
    typedef pair<pt,int> p;     //pair存点与距离,方便队列
    int dx[4]={0,0,-1,1};       //X偏移,上下左右
    int dy[4]={1,-1,0,0};       //Y偏移,上下左右
    int main(){
        int n,m;cin>>n>>m;      //地图大小
        pt s,g;                 //定义起点与终点
        for(int i=1;i<=n;i++){  //遍历行
            for(int j=1;j<=m;j++){  //遍历列
                cin>>mp[i][j];      //输入
                if(mp[i][j]=='s'){  //如果是起点
                    s.x=i;      //记下X
                    s.y=j;      //记下Y
                }
                if(mp[i][j]=='g'){//如果是终点
                    g.x=i;      //记下X
                    g.y=j;      //记下Y
                }
    
            }
        }
        queue<p>qu;             //开队列
        qu.push(p(s,0));        //压入起点
        while(!qu.empty()){     //非空
            pt nowp=qu.front().first;   //读出队首点
            int dis=qu.front().second;  //读出队首点到起点步数
            vis[nowp.x][nowp.y]=1;      //打上已访问标记
            qu.pop();                   //弹出队首
            if(nowp.x==g.x&&nowp.y==g.y){cout<<dis<<endl;return 0;}     //到终点跳出
            for(int i=0;i<4;i++){   //未到终点则四个方向偏移
                pt newp;            //定义新点
                newp.x=nowp.x+dx[i];if(newp.x<1 || newp.x>n)continue;   //得新X,超限跳过
                newp.y=nowp.y+dy[i];if(newp.y<1 || newp.y>m)continue;   //得新Y,超限跳过
                if(vis[newp.x][newp.y]==0&&mp[newp.x][newp.y]!='*'){    //未访问且可行
                    qu.push(p(newp,dis+1));                             //新点压入队列
                }
            }
        }
        cout<<"impossible"<<endl;   //队空都走不到,就肯定走不到了
        return 0;
    }
    /*
    in
    3 3
    s..
    ...
    g..
    out
    2
    in
    3 3
    s..
    **.
    g..
    out
    6
    in
    3 3
    s..
    ***
    g..
    out
    impossible
    */
    
    
    展开全文
  • bfs

    2016-08-23 17:07:21
    bfs

    题意

    给定一个有向无子环无重边的图,给定起点和终点,给定a,b,c三种路径长度,求最小次数ans,使得无论如何从a,b,c中选择ans次,均能在ans次之内走到终点

    思路

    1.预处理出某个点走a,b,c步后能否到达某个点
    2.从终点bfs,倒着扩展能到达的其他点,因为若一个点走a,b,c步后均能到达必胜点则从该点出发也能达到终点,且步数为能到达的必胜点中最大的+1

    code

    Sibling Rivalry

    展开全文
  • BFS

    在上一篇的基础上,发现 BFS 只能对与边权相同的图求最短路。实际上,在这篇要记录的题目中可以知道一张图中如果只有两种边权,那么最短路也是可以用 BFS 来求的,并且时间复杂度较低。

    题目
    达达是来自异世界的魔女,她在漫无目的地四处漂流的时候,遇到了善良的少女翰翰,从而被收留在地球上。翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障,导致无法启动。电路板的整体结构是一个 RRCC 列的网格R,C500(R,C≤500),如下图所示。
    在这里插入图片描述

    每个格点都是电线的接点,每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后,它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源,右下角的接点接入飞行车的发动装置。
    达达发现因为某些元件的方向不小心发生了改变,电路板可能处于断路的状态。她准备通过计算,旋转最少数量的元件,使电源与发动装置通过若干条短缆相连。不过,电路的规模实在是太大了,达达并不擅长编程,希望你能够帮她解决这个问题。
    注意:只能走斜向的线段,水平和竖直线段不能走。

    输入格式
    输入文件包含多组测试数据。
    第一行包含一个整数 TT ,表示测试数据的数目。
    对于每组测试数据,第一行包含正整数 RRCC ,表示电路板的行数和列数。
    之后R行,每行 CC 个字符,字符是"/“和”"中的一个,表示标准件的方向。

    输出格式
    对于每组测试数据,在单独的一行输出一个正整数,表示所需的缩小旋转次数。
    如果无论怎样都不能使得电源和发动机之间连通,输出NO SOLUTION。

    数据范围
    1R,C500,1≤R,C≤500,
    1T51≤T≤5
    测评地址

    解法:把网格图的每个格点看成节点,当想从一个节点走到别的节点上时,如果原图中的线路允许则边权为0,如果需要旋转则为1。此时,再用 BFS 来求最短路,不过在搜索树上,边权为0的点应该在边权为1的点前被扩展,因此采取双端队列,若边权为0,则插入队头,否则插入队尾。
    注意
    1、输入的“\”和“/”的处理要细心!
    2、其实图中有一些节点是永远不可能走到的,因为走一步横纵坐标均变化1,因此必须与起点奇偶性相同才可以,这样也可以判断 NO SOLUTION 的情况。

    代码

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <deque>
    
    #define x first
    #define y second
    
    using namespace std;
    
    const int N=510;
    
    typedef pair<int ,int> pii;
    
    int T;
    int n,m;
    deque<pii> q;
    char g[N][N];
    int dist[N][N];
    bool v[N][N];
    
    void bfs(){
    
        q.push_back({0,0});
        
        int dx[4]={-1,1,-1,1};
        int dy[4]={-1,-1,1,1};
        int ix[4]={-1,0,-1,0};
        int iy[4]={-1,-1,0,0};  //*details!!
        
        char s[5]="\\//\\";  //det!
        
        memset(v,0,sizeof(v));
        memset(dist,0x3f,sizeof(dist));
        dist[0][0]=0;
        
        while(q.size()){
            
            pii t=q.front(); //*
            q.pop_front(); //*
            
            //if(t.x==n && t.y==m) return ;
            if(v[t.x][t.y]) continue;
            v[t.x][t.y]=1;
            
            for(int i=0;i<4;i++){
                int nx=t.x+dx[i],ny=t.y+dy[i];
                if(nx<0 || nx>n || ny<0 || ny>m) continue;
                
                int gx=t.x+ix[i],gy=t.y+iy[i];
                int w=(g[gx][gy]!=s[i]);
                int d=dist[t.x][t.y]+w;
                if(d<=dist[nx][ny]){
                    dist[nx][ny]=d;
                    if(!w) q.push_front({nx,ny});
                    else q.push_back({nx,ny});
                }
            }
        }
        
    }
    
    int main(){
        cin>>T;
        while(T--){
            cin>>n>>m;
            for(int i=0;i<n;i++) cin>>g[i];
            bfs();
            if((n+m)%2) cout<<"NO SOLUTION"<<endl;
            else cout<<dist[n][m]<<endl;
        }
        return 0;
    }
    
    展开全文
  • BFS

    上一篇搜索的博客讲了 BFS 一个经典的应用模型,这篇讲述另一个经典模型的一点小扩展。另一个 BFS 的经典应用模型是求一张具有相同边权的图上的单源点最短路,如果是多源点的最短路,实际上也是可以用 BFS 来解决的,
    先看题目

    给定一个 NNMM 列的01矩阵 AAA[i][j]A[i][j]A[k][l]A[k][l] 之间的曼哈顿距离定义为:
    dist(A[i][j],A[k][l])=ik+jldist(A[i][j],A[k][l])=|i−k|+|j−l|
    输出一个 NNMM 列的整数矩阵 BB,其中:
    B[i][j]=min1xN,1yM,A[x][y]=1dist(A[i][j],A[x][y])B[i][j]=min_{1≤x≤N,1≤y≤M,A[x][y]=1}dist(A[i][j],A[x][y])
    数据范围:1N,M10001≤N,M≤1000
    测试地址

    人话:求每一个0到离她最近的1的曼哈顿距离。

    做法:将所有为零的点加入队列再进行 BFS 求最短路即可。
    解释:BFS实际上就是最多在一颗搜索树的两层上扩展更新。而原先的单源点求最短路是以唯一的起点为根节点进行 BFS,在这道题里,我们可以不去管根节点是否只有一个,或者说加一个虚拟的超级根节点,她到每个0的边的权为0,然后再进行正常的 BFS 即可。

    代码

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int,int> pii;
    
    const int N=1010;
    
    int g[N][N],n,m;
    pii q[N*N];
    int d[N][N];
    
    void bfs(){
        int hh=0,tt=-1;
        memset(d,-1,sizeof(d));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(g[i][j]==1){
                    d[i][j]=0;
                    q[++tt]={i,j};
                }
        
        int dx[4]={0,1,0,-1};
        int dy[4]={-1,0,1,0};
                
        while(hh<=tt){
            pii t=q[hh++];
            for(int i=0;i<4;i++)
            {
                    int nx=t.x+dx[i],ny=t.y+dy[i];
                    if(nx<=0 || nx>n || ny<=0 || ny>m) continue;
                    if(d[nx][ny]!=-1) continue;
                    d[nx][ny]=d[t.x][t.y]+1;
                    q[++tt]={nx,ny};
                }
        }
    }
    
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%1d",&g[i][j]);
                
        bfs();
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                printf("%d ",d[i][j]);
            printf("\n");
        }
        
        return 0;
    }
    
    展开全文
  • CBFS连接--企鹅578867473索取Crack 在Windows应用程序中创建和管理虚拟文件系统。 CBFS筛选器 跟踪和控制文件系统,注册表以及流程管理器操作。 CBFS存储 在任何地方创建并嵌入安全的,功能齐全的文件系统。 ...
  • 广度优先搜索BFS bfs

    2020-05-02 14:11:30
    广度优先搜索BFS bfs 广度优先搜索,又称宽度优先搜索,简称 bfs,我们以后都会用 bfs 来表示广度优先搜索。与深度优先搜索不同的是,广度优先搜索会先将与起始点距离较近的点搜索完毕,再继续搜索较远的点,而深搜...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 64,865
精华内容 25,946
关键字:

bfs