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

    千次阅读 多人点赞 2020-02-02 18:59:11
    bfs原理 bfs就是广度优先搜索,与深度优先搜索有类似之处也有不同之处。 深度优先搜索是不撞南墙不回头的莽夫。 广度优先搜索则像高塔一样稳健。 bfs要先建立一个队列 struct node { int ;//至少两个,一个表示...

    bfs原理

    bfs就是广度优先搜索,与深度优先搜索有类似之处也有不同之处。
    深度优先搜索是不撞南墙不回头的莽夫。

    而广度优先搜索则像高塔一样稳健。
    在这里插入图片描述
    所以说广度优先搜索总是能找到一个问题的最优解,但它没有深搜那么莽夫,所以广搜所要花费的时间往往比深搜要久。

    bfs的建立

    bfs要先建立一个队列

    struct node
    {
    	int ;//至少两个,一个表示数据,一个表示数据所在的位置。
    };
    

    用这个结构体来表示每一步与每一步所在的位置。

    区别

    dfs考虑的是当先该怎么做并用递归写出下一次,而bfs考虑的是下一次有几种做法
    我这里给出dfs的文章做对比dfs原理

    例题

    为了直观的显现出bfs与dfs的区别,我们用bfs来解我之前在dfs上的原题:

    B先生在一个迷宫里迷路了,他需要A先生的救助,A先生也不知道怎么走,所以他只能一步一步试。
    现在编程来帮A先生解救B先生。

    输入

    m,n代表迷宫的长与宽。
    m行,n列0或1.其中0代表路,1代表障碍。
    出发坐标(x,y)与目标坐标(sx,sy)

    输出

    最短步数。

    输入样例

    5 4
    0 0 1 0
    0 0 0 0
    0 0 1 0
    0 1 0 0
    0 0 0 1
    1 1 4 3
    

    输出样例

    7
    

    我们先建立一个结构体

    #include<stdio.h>
    struct node
    {
    	int x,y,s;//x,y为坐标,s为步数。
    };
    

    接下来是地图初始化与输入

    truct node que[2501];//地图
     	int a[51][51]={0},book[51][51]={0};
     	int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//方向
     	int head,tail;
     	int i,j,k,m,n,sx,sy,p,q,tx,ty,flag;
     	scanf("%d%d",&n,&m);//初始化地图
     	for(i=1;i<=n;++i)
     		for(j=1;j<=m;++j)
     			scanf("%d",&a[i][j]);
     	scanf("%d%d%d%d",&sx,&sy,&p,&q);//队列初始化
     	head=1;    //其他值的初始化
     	tail=1;
     	que[tail].x=sx;
     	que[tail].y=sy;
     	que[tail].s=0;
     	tail++;
     	book[sx][sy]=1;
     	flag=0;
    

    接下来是bfs的关键

    如果用dfs,我们就用一个dfs函数来模拟每一步。

    void dfs(int x,int y,int step)
    {
    	int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    	int i,nx,ny;
    	if(x==p&&y==q){
    		if(step<min)
    			min=step;
    		return;
    	}	
    	for(i=0;i<=3;++i){
    		nx=x+next[i][0];
    		ny=y+next[i][1];
    		if(nx<1||ny<1||nx>n||ny>m)
    			continue;
    		if(a[nx][ny]==0&&book[nx][ny]==0){
    			book[nx][ny]=1;
    			dfs(nx,ny,step+1);
    			book[nx][ny]=0;
    		}	
    	}
    	return;
    }
    

    如果用bfs则:

    1. 首先判断这个地方走没走过 *head<tail*
    2. 列举四分方向

    for(k=0;k<=3;++k){
     			tx=que[head].x+next[k][0];
     			ty=que[head].y+next[k][1];
     			if(tx<1||tx>n||ty<1||ty>m)
     				continue;
     			if(a[tx][ty]==0&&book[tx][ty]==0){//这里判断这一步是否走过
     				book[tx][ty]=1;
     				que[tail].x=tx;
     				que[tail].y=ty;
     				que[tail].s=que[head].s+1;
     				tail++;
    			}
    

    3.如果找到目的地了flag=1;break;

    if(tx==p&&ty==q){
    	flag=1;
    	break;
    }
    

    4.如果flag=1;则代表这里条路已经走完了,则进行下一次尝试head++

    bfs部分完整代码:

    while(head<tail){
     		for(k=0;k<=3;++k){
     			tx=que[head].x+next[k][0];
     			ty=que[head].y+next[k][1];
     			if(tx<1||tx>n||ty<1||ty>m)
     				continue;
     			if(a[tx][ty]==0&&book[tx][ty]==0){//和dfs一样乱七八糟的判断
     				book[tx][ty]=1;
     				que[tail].x=tx;
     				que[tail].y=ty;
     				que[tail].s=que[head].s+1;
     				tail++;
    			}
    			 if(tx==p&&ty==q){
    			 	flag=1;
    			 	break;
    			}
    		}
    		if(flag==1)
    			break;
    		head++;
    	}
    

    在进行完这些步骤之后。最少的步数就模拟出来了。
    接下来只需要进行一个简单的printf即可。

    完整代码

    #include<stdio.h>
    struct node
    {
    	int x,y,s;//x,y为坐标,s为步数。
    };
     
     int main()
    {
    	struct node que[2501];//地图
     	int a[51][51]={0},book[51][51]={0};
     	int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//方向
     	int head,tail;
     	int i,j,k,m,n,sx,sy,p,q,tx,ty,flag;
     	scanf("%d%d",&n,&m);//初始化地图
     	for(i=1;i<=n;++i)
     		for(j=1;j<=m;++j)
     			scanf("%d",&a[i][j]);
     	scanf("%d%d%d%d",&sx,&sy,&p,&q);//队列初始化
     	head=1;
     	tail=1;
     	que[tail].x=sx;
     	que[tail].y=sy;
     	que[tail].s=0;
     	tail++;
     	book[sx][sy]=1;
     	flag=0;
     	while(head<tail){
     		for(k=0;k<=3;++k){
     			tx=que[head].x+next[k][0];
     			ty=que[head].y+next[k][1];
     			if(tx<1||tx>n||ty<1||ty>m)
     				continue;
     			if(a[tx][ty]==0&&book[tx][ty]==0){//和dfs一样乱七八糟的判断
     				book[tx][ty]=1;
     				que[tail].x=tx;
     				que[tail].y=ty;
     				que[tail].s=que[head].s+1;
     				tail++;
    			}
    			 if(tx==p&&ty==q){
    			 	flag=1;
    			 	break;
    			}
    		}
    		if(flag==1)
    			break;
    		head++;
    	}
    	printf("%d",que[tail-1].s);
    	return 0;
    }
    
    展开全文
  • 估计很多初学者对这个问题一直不明白,为什么使用 BFS 进行广度搜索,一定可以搜索到最短路径。 讲真,在学校里学习 BFS 的时候,自己也没完全明白为什么。老师这么教,课本这么写,我就这么记。 其实回答这个问题很...
  • BFS解决八数码问题

    2020-12-29 10:31:11
    在图1,3*3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空。 如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态(图1左)到目标状态(图1右)。...
  • 最终效果是实现了Prim随机生成迷宫,BFS&DFS路径显示、最短路长度显示、过程动态展示,主函数中有菜单,操作方便。 不仅可以用来读代码长知识、还可以用作算法演示。 附带第五版的exe文件,欢迎使用!
  • 人工智能大作业:c++代码bfs解决8数码问题
  • 使用python实现八数码问题的宽度优先搜索
  • 广度优先搜索构建迷宫(BFS算法)动态构建过程的python 源代码,详情请移步本人博客<迷宫与寻路可视化(二)广度优先搜索构建迷宫(BFS算法)>
  • BFS算法和数据集的顺序版本摘自所著的 介绍 使用Spark进行无向图处理的并行广度优先搜索算法 安装 要求: JDK 7 , Maven , Spark 在service.properties文件中配置服务参数。 ####使用IDE运行 将库从sequence-...
  • 以动画的方式采用bfs算法实现八数码问题的解决,html文件可直接运行
  • 规格为A4纸或A3纸折叠 佛山科学技术学院用四号宋体 实 验 报 告用小二号黑体 课程名称 数据结构实验 实验项目 实现DFS和BFS算法 专业班级 姓 名 学 号 指导教师 成 绩 日 期 用小四号宋体 一目的与要求 1通过本实验...
  • 本程序实现了对一颗树的广度优先搜索,通过本程序还可以判断图的连通性
  • FPGA上的BFS 介绍 在我们的最终项目中,有一部分算法的原理与BFS相似,因此我计划使用FPGA加速简单的BFS算法。 如果仍有空间,请使用加速的BFS算法作为模板来对我们项目的相应部分进行修改,以使用FPGA加速项目。 ...
  • BFS

    千次阅读 2017-10-12 16:27:10
    BFS -> 僵尸感染 -> 队列每个点状态的数量 ,每个状态访问一次int visted = [x][y][状态数量]; Queue queue;void bfs(起点){ if起点符合退出条件,return 起点入队 while(队列不为空){ 当前临时点 = queue出队 ...

    BFS -> 僵尸感染 -> 队列

    每个点状态的数量 ,每个状态访问一次,想办法将状态转换为int(类似hash)

    int visted = [x][y][状态数量];
    Queue queue;

    void bfs(起点){
    if起点符合退出条件,return

      起点入队
      while(队列不为空){
          当前临时点 = queue出队
          for(各个方向遍历){
              根据当前临时点得到下一个点的位置
             if(下一个点的visted没有访问过&&其他条件成立)
                 下一个点入队
                 更新下一个的信息(比如到达step)
                 如果符合退出条件,return
                 else 继续
             }
          } 
     }
    

    }

    POJ 1324

    #include <cstdio>
    #include <iostream>
    
    using namespace std;
    #define SIZE 20
    #define LENGTH 8
    #define SNAKE_STATES 16384 //状态数量,以蛇头为起点,向后的每个点都有4中状态(取整),就提取了特征值
    
    int snake[LENGTH][2];
    int stone[SIZE * SIZE][2];
    
    int visited[SIZE + 1][SIZE + 1][SNAKE_STATES];
    typedef struct Element{
        int x;
        int y;
        int state;
        int step;
    } Element;
    
    Element Queue[SIZE * SIZE * SNAKE_STATES];
    int head, tail;
    
    
    int direct[3][3] = {
        0, 0, 0,
        3, 0, 1,
        0, 2, 0,
    };
    
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    
    int getState(int Len){
        int state = 0;
        for(int i = Len - 1; i > 0; i--){
            int x = snake[i][0] - snake[i - 1][0];
            int y = snake[i][1] - snake[i - 1][1];
            x+=1;
            y+=1;
            int D = direct[x][y];
            state = state * 4 + D;
        }
        return state;
    }
    
    int isStone(int x, int y, int K){
        for(int i = 0; i < K; i++){
            if(x == stone[i][0] && y == stone[i][1])
                return 1;
        }
        return 0;
    }
    
    int isSnake(int x, int y, int state, int L, int nx, int ny){
        snake[0][0] = x;
        snake[0][1] = y;
        for(int i = 1; i < L; i++){
            int D = state % 4;
            state = state / 4;
            snake[i][0] = snake[i - 1][0] + dx[D];
            snake[i][1] = snake[i - 1][1] + dy[D];
        }
        for(int i = 0; i < L; i++){
            if(nx == snake[i][0] && ny == snake[i][1]){
                return 1;
            }
        }
        return 0;
    }
    
    int getMinStep(int M, int N, int L, int K){
        Queue[tail].x = snake[0][0];
        Queue[tail].y = snake[0][1];
        Queue[tail].state = getState(L);
        Queue[tail].step = 0;
        visited[Queue[tail].x][Queue[tail].y][Queue[tail].state] = 1;
        if(Queue[tail].x == 1 && Queue[tail].y == 1) return 0;
        tail++;
        while(head < tail){
            Element curState = Queue[head++];
            //cout << "out " <<  curState.x << " " << curState.y << " " << curState.step << " " << curState.state << endl;
            for(int i = 0; i < 4; i++){
                int nx = curState.x + dx[i];
                int ny = curState.y + dy[i];
                int nd;
                if(i >= 2) nd = i - 2;
                else nd = i + 2;
                if(nx >= 1 && nx <= M && ny >= 1 && ny <= N){
                    int mask = (1 << (2 * L - 2)) - 1;
                    int nState = ((curState.state * 4) & mask) + nd;
                    if(!visited[nx][ny][nState] && !isStone(nx, ny, K) && !isSnake(curState.x, curState.y, curState.state, L, nx, ny)){
                        Queue[tail].x = nx;
                        Queue[tail].y = ny;
    
                        Queue[tail].state = nState;
                        Queue[tail].step = curState.step + 1;
    
                        //cout << "in " <<  nx << " " << ny << " " << Queue[tail].step << " " << nState << endl;
                        if(nx == 1 && ny == 1) return Queue[tail].step;
    
                        tail++;
                        visited[nx][ny][nState] = 1;
                    }
                }
            }
        }
        return -1;
    }
    
    int main(){
        //freopen("input.txt", "r", stdin);
        int nC = 1;
        while(1){
            int M, N, L;
            cin >> M >> N >> L;
            if(M + N + L == 0) break;
    
            for(int i = 0; i < L; i++){
                cin >> snake[i][0] >> snake[i][1];
            }
            int K;
            cin >> K;
            for(int i = 0; i < K; i++){
                cin >> stone[i][0] >> stone[i][1];
            }
            head = 0;
            tail = 0;
            for(int i = 0; i <= M; i++){
                for(int j = 0; j <= N; j++){
                    for(int k = 0; k < SNAKE_STATES; k++){
                        visited[i][j][k] = 0;
                    }
                }
            }
            int minStep = getMinStep(M, N, L, K);
            cout << "Case " << nC <<": "<< minStep << endl;
            nC++;
        }
    
    
        return 0;
    }
    
    展开全文
  • Java实现,完整可视化界面友好展示,,记录不同算法的效率
  • 二叉树的BFS和DFS

    2021-01-21 16:51:00
    1. ⼆叉树的直径 leetcode 543 / lintcode 1181 描述 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。...
  • GBFS_AStar-源码

    2021-03-19 23:22:13
    GBFS_AStar 这段代码是我在胡志明市(越南)理科大学的作业。 根据给定权重的图,根据相应算法从头到尾顶点找到最短路径。 每种算法返回的结果如下 GBFS:从原点到目标顶点的路径上的总启发式。 A *:从原点到目标...
  • Xilinx Zynq 上的混合 BFS 作者 Yaman Umuroglu ( ) 许可证和“学术免责声明” 本作品根据知识共享署名 4.0 国际许可协议获得许可。 要查看此许可证的副本,请访问或向美国知识管理署(Creative Commons)致函,...
  • 广度优先搜索(BFS)算法 bfs(G) > G = (V, E) > Initialize the vertex colors and predecessors 1 for each vertex v ϵ V 2 do color [v] = white 3 π[v] = null 4 for each vertex v ϵ V 5 do if color [v] = ...
  • 主要介绍了Java实现利用广度优先遍历(BFS)计算最短路径的方法,实例分析了广度优先遍历算法的原理与使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 本节内容 最短路径 BFS算法 王道考研/ 最短路径问题 6 R城 Y城 G港是个物流集散中经常需要往各个城市运东 10 怎么运送距离最近单源最短路径问题 9 2 6 G港 7 5 各个城市之间也需要互相往来相互之间怎么距离最 近每对...
  • 没啥事写的一个C++解最小步数二阶... 用的是广搜(BFS),效率算是比较高,平均结算7ms(笔记本八代i7),平均7~8步能复原,源码有比较细致的注释,配套一个简单的QT界面,具体的细节以及原理稍后更新,可见我博客。
  • 用js写了bfs和dfs解决八数码问题,移动过程可视化。包含2个html文件分别是dfs和bfs,Jquery,0-8一共9张图片。直接打开那两个html文件即可。
  • bfs (browser-end filesystem) 浏览器端文件系统API 项目说明 本项目仅仅适用于chrome高版本(chrome31+), 包括webkit内核浏览器; 项目源于百度凤巢离线物料管理项目 相关项目 应用示例 使用方法 读取文件内容 // ...
  • 定义 【假设先访问左子树在访问右子树】 那么广度遍历的顺序就是ABCDEF 从上到下,从左到右去访问 运用到格子游戏中,找寻某点到某点的路径 【假设只记录四方位(遍历顺序上左下右)】 向队列中存入起点,遍历该点...
  • 广度优先搜索算法BFS

    2017-04-24 18:56:18
    广度优先搜索算法—BFS的相关代码,包括循环队列的代码
  • (4)指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提示:使用一个队列实现BFS); (5)输入顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执行操作3);否则输出信息“无x...
  • 这是山东大学可视化课程项目,用js实现的BFS和DFS,详细的展示了BFS和DFS的运行过程,网页可交互。
  • 广度优先搜索(BFS) 深度优先搜索(DFS) 迭代深化搜索(IDS) 统一成本搜索(UCS)(Dijkstra算法) A *算法(A星) 我实现了上述算法,以找到任何给定图(状态空间图)的遍历路径和精确路径。 状态空间图...
  • BFS搜索 迷宫.cpp

    2020-10-13 15:53:29
    BFS搜索案例——走出迷宫。 广度优先搜索BFS(Breadth First Search)也称为宽度优先搜索,它是一种先生成的结点先扩展的策略。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 204,319
精华内容 81,727
关键字:

bfs