了解什么是BFS-程序员宅基地

技术标签: 算法  深度优先  算法竞赛进阶  宽度优先  

第十三讲 BFS

DFS复习

DFS深度优先搜索,是将问题抽象成一种树结构,带着目的性的进行搜索,一路走到底,直到达到目标。深度优先搜索借助递归来实现,递归下去,回溯上来,如果没有走到底就发现下面的元素都无法满足题目要求时,则停止对该路的搜索。

DFS遍历步骤(图示)
  1. 从根节点1开始搜索

在这里插入图片描述

  1. 找出与此点邻接的且尚未遍历的点

  2. 遍历完所有节点后,将栈中元素弹出,DFS完成

例题

面积计算(深搜)

分析:因为是要求闭合*围成的曲线,第一步把四周的0,以及该0的四周的0变成*号,之后再枚举0的个数即可。

#include<iostream>
#include<cstring>
using namespace std;
char a[55][55];
int dx[]={0,-1,1,0},dy[]={1,0,0,-1};//搜索上下左右,可以少写几个if 
int len=0;
void dfs(int x,int y){//参数为 为'0' 点的横纵坐标 
	a[x][y]='*';
	for(int i=0;i<4;i++){
		if(a[x+dx[i]][y+dy[i]]=='0')
			dfs(x+dx[i],y+dy[i]);
	}
	return;
}
int main(){
	cin>>a[0];
	int m=1;
	int len=strlen(a[0]);
	while(cin>>a[m]) ++m;
	for(int i=0;i<m;i++){//从边界开始搜索,将外围的染黑 
		if(a[i][0]=='0')
			dfs(i,0);
		if(a[i][len-1]=='0')
			dfs(i,len-1);
	}
	for(int i=0;i<len;i++){
		if(a[0][i]=='0')
			dfs(0,i);
		if(a[m-1][i]=='0')
			dfs(m-1,i);
	}
	int sum=0;
	for(int i=0;i<m;i++)
		for(int j=0;j<len;j++)
			if(a[i][j]=='0')
				sum++;
	cout<<sum;
}

BFS

BFS与DFS的区别与联系

BFS和DFS都属于优先搜索算法,BFS又称宽度优先搜索,它们的主要区别在于搜索方式不同,DFS是一个劲往下搜索并带有目的性的搜索,当不满足条件时就回溯,而BFS是一层一层的遍历。

数据结构 空间复杂度 可以解决的问题
DFS O(h) 具体问题具体分析
BFS 队列 O(2^n) 权值相同的最短路问题

如果按照BFS遍历该图中的元素,遍历顺序为 1->2->8->3->5->6->9->4->7

BFS模板

广度优先搜索算法的基本思想:
1、对于初始状态入队,设置初始状态为已访问
2、如果队列不为空时,出队队头元素,否则跳到第5步
3、检查出队的元素是否为最终解,如果是则跳到第5步。
4、对于出队的元素,检查所有相邻状态,如果有效并且未访问,则将
所有有效的相邻状态进行入队,并且设置这些状态为已访问,然后
跳到第2步重复执行
5、检查最后出队的元素是否为最终解,如果是输出结果,否则说明无解

void bfs(){
	queue<int>q;
	st[1]=1;//说明第一个点已经遍历过了 
	q.push(1);//把第一个变量入队
	while(q.size()) {
		int t=q.front();//取出队头元素 
		q.pop();
		for(根据实际问题分析,遍历跟这个点相关的点){
		if(满足题目的条件){
			q.push(将该点入队);
		} 
	}
}
为什么BFS能解决最短路问题?

如果要求图中 点1 和点4之间的最短路径,用BFS是十分好求的,为什么很容易,因为BFS是一层一层的遍历,它先遍历离顶点距离为1 的点,再遍历与顶点距离为2的点……

但是BFS只能解决权值相同的最短路问题,如果想要解决其他类型的最短路问题,需要用到其他的算法,以后在图论章节中会学到。

救援行动

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HVbfSHBP-1639307459303)(C:\Users\ZZWGY\AppData\Roaming\Typora\typora-user-images\image-20211209092730639.png)]

这道题求最短时间,并且移动一步所需要的时间是相同的

#include <iostream>
#include <cstdio>
#include <queue>
#include<cstring>
using namespace std;
int n,m,flag=0;
int dx[]={1,0,0,-1},dy[]={0,-1,1,0};
int vis[205][205];
string w[205];
bool valid(int x,int y){
	return x>=0&&x<n&&y>=0&&y<m;
}
struct man
{
    int x,y,step;
};
queue<man>q;
void bfs(man s)
{
    q.push(s);//将营救队员初始位置入队 
    while(!q.empty())//队列非空 
    {
        man t=q.front();
        //printf("%d %d %d\n",t.x,t.y,t.step);
        if(w[t.x][t.y]=='a'){printf("%d\n",t.step);flag=1;return;}//如果走到'a'点,就结束 
        else if(w[t.x][t.y]=='x'){t.step++;q.pop();q.push(t);w[t.x][t.y]='.';continue;}//遇到怪兽就把时间+1,再重新入队 
        q.pop();
        for(int i=0;i<4;i++)//上下左右搜索 
        {
            int xx=t.x+dx[i];int yy=t.y+dy[i];
            if(valid(xx,yy)&&vis[xx][yy]==0&&w[xx][yy]!='#')
            {
                man k;
                vis[xx][yy]=1;
                k.step=t.step+1;k.x=xx;k.y=yy;q.push(k);
            }
        }
    }
}
int main()
{
    memset(vis,0,sizeof(vis));
    scanf("%d%d",&n,&m);
	man s;
    for(int i=0;i<n;i++)cin>>w[i];//输入地图 
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        {
            if(w[i][j]=='r')//初始化营救队员所站的位置 
            {
 
                s.x=i;
                s.y=j;
                s.step=0;
            }
        }
    bfs(s);
    if(flag==0)printf("NO ANSWER\n");
    return 0;
}

面积计算(宽搜)

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
char a[1500][250];
int dx[]={0,0,-1,1},dy[]={-1,1,0,0},len,k;//用dx,dy数组记录上下左右搜索坐标的变化情况 
bool valid(int x,int y){//判断新坐标是否越界 
	return x>=1&&x<k&&y>=1&&y<=len;
}
void bfs(int x,int y){
	a[x][y]='1';//将为0的点变为1 
	PII t=make_pair(x,y);//看不懂这个语句的,自行搜索STL 中的pair模板 
	queue<PII> q;
	q.push(t);// 将该点坐标放进队头
	while(q.size()){
		PII t=q.front();//队头出队 
		q.pop();
		for(int i=0;i<4;i++){//向它的四周搜素 
			int x1=t.first+dx[i];
			int y1=t.second+dy[i];
			if(valid(x1,y1)&&a[x1][y1]=='0'){//将新的符合条件的点入队 
				a[x1][y1]='1';
				PII t=make_pair(x1,y1);
				q.push(t);
			}
		}
	}
}
int main(){
	k=1;
	cin>>(a[k++]+1);
	while(cin>>(a[k]+1)){
		k++;
	}
	len=strlen(a[1]+1);
	for(int i=1;i<k;i++){
		if(a[i][1]=='0'){
			bfs(i,1);
		}
		if(a[i][len]=='0'){
			bfs(i,len);
		}
		
	}
	for(int i=1;i<=len;i++){
		if(a[1][i]=='0')
			bfs(1,i);//如果边界点为0,就向它上下左右四个方向搜索 
		if(a[k-1][i]=='0')
			bfs(k-1,i);
	}
	int sum=0;
	for(int i=1;i<k;i++)
		for(int j=1;j<=len;j++)
			if(a[i][j]=='0')
				sum++;
	cout<<sum<<endl;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_42376883/article/details/121891893

智能推荐

connect to server ip fail java.net.SocketTimeoutException: connect timed out_failed to connect to server connection timed out-程序员宅基地

文章浏览阅读725次。这个问题是在使用junit测试时出现的,就是需要关闭centos7的防火墙systemctl stop firewalld.service@SpringBootTest@RunWith(SpringRunner.class)public class TestFastDFS { //测试上传 @Test public void testUpdate() { ..._failed to connect to server connection timed out

java怎么创建局部变量_Java使用getter in for循环或创建一个局部变量?-程序员宅基地

文章浏览阅读250次。作为Rogério answered,在循环之外获取对象引用(Object object = example.getValue();)可能比在循环中调用getter更快(或至少不会更慢),因为在“最糟糕”的情况下,example.getValue()可能会在背景中做一些非常计算上昂贵的东西,尽管getter methods应该是“微不足道的”.通过分配引用一次并重新使用它,您只需执行一次昂贵的计算..._创建一个带局部变量的function java

java饮料_品尝饮料java代码-程序员宅基地

文章浏览阅读1.9k次。题目:品尝饮料时间:2018-1-5一、要求1、使用命令行参数(饮料类型),输出该饮料类型的味道,如:当命令行参数为1时,结果见如下:咖啡:苦2、如果没有该种饮料,结果见如下:对不起!没有您输入的饮料类型。二、推荐实现步骤1、建立一个Java抽象类Drink,应当:a、声明一个抽象方法taste(),该方法负责输出饮料的味道;b、声明int型常量来代表不同的饮料类型(咖啡、啤酒、牛奶),如:1:咖..._三、品尝饮料 1.建立一个抽象类drink,应当: (1)声明一个抽象方法taste(),该方法负

android 弹出输入框 输入法,(转)android开发-输入法弹出遮挡编辑框问题-程序员宅基地

文章浏览阅读618次。当我们做一个发送消息布局的时候,编辑框往往是在下面,而输入法弹出的时候就会吧编辑框完全遮挡,导致看不见输入框,这样用户体验就会很差!下面9种设置,可能会解决你在输入法上碰到的一些问题android:windowSoftInputMode=“adjustPan” 在Manifest.xml 属性一共有9个取值,分别是:stateUnspecified,stateUnchanged,stateHi..._stateunchanged

计算机描述不可用win10,升级win10出现的各种问题及解决办法-程序员宅基地

文章浏览阅读2.5k次。将电脑从以前版本的 Windows-如 Windows 7 或 Windows 8.1-升级到 Windows 10。本常见问题解答旨在解决有关升级到 Windows 10 的问题。本文将针对Win10的一些常见问题给出解决方案,如果你在使用Win10的过程中,遇到了无限重启、不能使用打印机和无法与Windows XP直接共享等问题,那这篇文章可能对你有帮助。升级win10出现的各种问题汇..._win10有问题

linux两个终端间通信,不同vlan间的通信简单配置(三种方式)-程序员宅基地

文章浏览阅读1k次。不同vlan间的通信简单配置1.单臂路由(图)环境:一台路由器,一台二层交换机,两台pc机二层交换机的配置一般模式:Switch>输入enable进入特权模式:Switch>enable输入configure terminal进入全局配置模式:Switch#configure terminalEnter configuration commands, one per line. En..._配置vlan使两台linux服务器互通

随便推点

android 编译完后镜像在哪个文件夹,android 镜像文件打包和解压-程序员宅基地

文章浏览阅读672次。android 源码编译后得到system.img,ramdisk.img,userdata.img映像文件。其中, ramdisk.img是emulator的 文件系统,system.img包括了主要的包、库等文件,userdata.img包括了一些用户数据,emulator负责加载这3个映像文件后,会 把system.img和userdata.img分别加载到 ramdisk文件系统中的sys..._android rootdir 编译到哪个镜像里

在VS2013下运行VS2010的项目 错误:Building an MFC project for a non-Unicode character set is deprecated_vs的unicode错误-程序员宅基地

文章浏览阅读267次。当使用VS2013运行VS2010项目的时候,会提示升级VC++,点击确定但是运行调试的时候,还是会出错,找不到mfc100d.dll,msvcr100d.dll上网搜索,找办法安装XXX库之后,依旧不行**错误:**Building an MFC project for a non-Unicode character set is deprecated解决办法:微软解释用于多字节..._vs的unicode错误

automake生成静态库文件_visual studio lib和dll的编译生成与调用-程序员宅基地

文章浏览阅读142次。Dll在Windows下,DLL(Dynamic Link Library,动态链接库)是一个被编译过的二进制程序,但与.exe文件不同,.dll文件不能独立运行,必须由其他程序调用。为什么有这东西呢?当然有其存在的好处啦:不限语言。我们可以用自己熟悉的语言写DLL,然后由其他语言写的可执行程序来调用这些DLL。例如,可以用Python写程序的主界面,然后调用C写的实现一个具体功能的DLL模块。增..._automake,vs

python+selenium自动化软件测试(unittes)-程序员宅基地

文章浏览阅读5.1k次。1.1 unittest简介前言(python基础比较弱的,建议大家多花点时间把基础语法学好,这里有套视频,可以照着练习下:http://pan.baidu.com/s/1i44jZdb密码:92fs)熟悉java的应该都清楚常见的单元测试框架Junit和TestNG,这个招聘的需求上也是经常见到的。python里面也有单元测试框架-unittest,相当于是一个python版的junit。..._python+selenium+unittes分层

PSIM软件学习---01初识别PSIM软件-程序员宅基地

文章浏览阅读1w次,点赞14次,收藏70次。  PSIM是趋向于电力电子领域以及电机控制领域的仿真应用包软件。PSIM全称Power Simulation。PSIM是由SIMCAD 和SIMVIEM两个软件来组成的。  PSIM软件最大的特点是支持C语言模块,这样在仿真电路时,特别是数字电源或者电机驱动仿真时,可以直接编写C代码来驱动功率管,调试电路非常方便。  但是PSIM仿真软件在网上的教程比较少,学习起来比较困难,当时自己学习的时候也废了好大的功夫,于是决定写一个系列的文章,来比较全面的介绍一下PSIM软件的使用。由于自己也是刚学会不久,如_psim

odoo tree视图属性_"odoo editable=\"top"-程序员宅基地

文章浏览阅读238次。一般属性列表颜色常用判断格式:编辑属性 editableeditable=“bottom”是在行的底部创建2.editable=“top”是在行的顶部创建_"odoo editable=\"top"

推荐文章

热门文章

相关标签