Breadth-First-Search
1. 与DFS的异同
相同点:搜索所有可能的状态。
不同点:搜索顺序。
2. BFS总是先搜索距离初始状态近的状态,它是按照:开始状态->只需一次转移就可到达的所有状态->只需两次转移就可到达的所有状态->……
对同一状态只搜索一次,因此复杂度为O(状态数*转移方式)。
3. DFS隐式地利用了栈,而BFS利用了队列,搜索时先将初始状态入队,此后出队取出状态,并把该状态可转移到的状态中尚未访问的状态入队,
重复上述过程,直到队列为空或找到解。观察队列我们可以得知,所有状态都是按距初始状态由近及远遍历的。
下面给出经典例题:迷宫最短路径
description:
给定一个大小为N*M的迷宫。迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。请注意,本题假定从起点一定可以移动到终点。
样例输入输出:
输入:
输出:
22
AC Code:
int INF=0x3f3f3f3f;
typedef pair<int,int> P;
int N,M,sx,sy,gx,gy;
char maze[N][M];
int d[N][M];//记录到各位置的最短距离
int dx[]={,,-,},dy={,,,-};
int bfs(){
queue<P> q; q.push(P(sx,sy));
memset(d,INF,sizeof(d));
d[sx][sy]=;
while(!q.empty()){
P p=q.front(); q.pop();
if(p.first ==gx&&p.second ==gy) break;
for(int i=;i<;i++){
int nx=P.first +dx[i],ny=P.second +dy[i];
if(nx>=&&nx<N&&ny>=&&ny<M&&maze[nx][ny]!='#'&&d[nx][ny]==INF){
q.push(P(nx,ny));
d[nx][ny]=d[p.first ][p.second]+;
}
}
}
return d[gx][gy];
}
宽度优先搜索BFS(Breadth-First-Search)的更多相关文章
-
【算法入门】广度/宽度优先搜索(BFS)
广度/宽度优先搜索(BFS) [算法入门] 1.前言 广度优先搜索(也称宽度优先搜索,缩写BFS,以下采用广度来描述)是连通图的一种遍历策略.因为它的思想是从一个顶点V0开始,辐射状地优先遍历其周围较 ...
-
挑战程序2.1.5 穷竭搜索>;>;宽度优先搜索
先对比一下DFS和BFS 深度优先搜索DFS 宽度优先搜索BFS 明显可以看出搜索顺序不同. DFS是搜索单条路径到 ...
-
【BFS宽度优先搜索】
一.求所有顶点到s顶点的最小步数 //BFS宽度优先搜索 #include<iostream> using namespace std; #include<queue> # ...
-
层层递进——宽度优先搜索(BFS)
问题引入 我们接着上次“解救小哈”的问题继续探索,不过这次是用宽度优先搜索(BFS). 注:问题来源可以点击这里 http://www.cnblogs.com/OctoptusLian/p/74296 ...
-
BFS算法的优化 双向宽度优先搜索
双向宽度优先搜索 (Bidirectional BFS) 算法适用于如下的场景: 无向图 所有边的长度都为 1 或者长度都一样 同时给出了起点和终点 以上 3 个条件都满足的时候,可以使用双向宽度优先 ...
-
广度优先搜索(Breadth First Search, BFS)
广度优先搜索(Breadth First Search, BFS) BFS算法实现的一般思路为: // BFS void BFS(int s){ queue<int> q; // 定义一个 ...
-
[宽度优先搜索] FZU-2150 Fire Game
Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns) ...
-
宽度优先搜索--------迷宫的最短路径问题(dfs)
宽度优先搜索运用了队列(queue)在unility头文件中 源代码 #include<iostream>#include<cstdio>#include<queue&g ...
-
宽度优先搜索(BFS)— 20180909 - 20180917
BFS几类题: 1.图的遍历:a.层级遍历 b.由点及面 c.拓扑排序 2.简单图最短路径: 简单图:1.无向图 2.边权重一致 图的时间复杂度: N个点,M条边,M最大是N^2,时间复杂度O(N+M ...
随机推荐
-
SPSS数据分析—分段回归
在SPSS非线性回归过程中,我们讲到了损失函数按钮可以自定义损失函数,但是还有一个约束按钮没有讲到,该按钮的功能是对自 定义的损失函数的参数设定条件,这些条件通常是由逻辑表达式组成,这就使得损失函数具 ...
-
paip.java 调用c++ dll so总结
paip.java 调用c++ dll so总结 ///////JNA (这个ms sun 的) 我目前正做着一个相关的项目,说白了JNA就是JNI的替代品,以前用JNI需要编译一层中间库,现在JNA ...
-
[转] - 如何用QTcpSocket传送图片
我们知道,tcp网络编程发送数据是利用套接字来实现,将要传输的东西转化为数据流再进行传输,为了确保数据传输的准确性和安全性,我们在发送数据流前发送一个quint32的常量来表示所要发送的数据的大小:当 ...
-
解决不安装VC运行库(VC2005,VC2008),程序运行出错的方法
因为VS2005以后程序采用了manifest的生成方式,所以发布的时候要和运行库一起发布.但是我们平时开发和发布的时候如果都要客户安装运行库,那就不太方便了.你可以Microsoft下载:http: ...
-
php创建读取 word.doc文档
创建文档; <?php $html = "this is question"; for($i=1;$i<=3;$i++){ $word = new word(); $w ...
-
自定义按钮~自适应布局~常见bug
一.元件 自定义按钮可用button或a display为 inline-block 方便设置格式,通过 padding,height,line-height,font-size设置按钮的大小 & ...
-
iOS 多线程 简单学习NSThread NSOperation GCD
1:首先简单介绍什么叫线程 可并发执行的,拥有最小系统资源,共享进程资源的基本调度单位. 共用堆,自有栈(官方资料说明iOS主线程栈大小为1M,其它线程为512K). 并发执行进度不可控,对非原子操作 ...
-
【算法】哈希表的诞生(Java)
参考资料 <算法(java)> — — Robert Sedgewick, Kevin Wayne <数据结构> ...
-
oracle drop table(表)数据恢复方法
今天不小心把系统用户表给drop掉了,正在运行的系统正式库啊,还好可以恢复 一.查看数据库回收站,看删除的表是否还在回收站select object_name,original_name,partit ...
-
C# 判断网卡类型以及其他网卡信息
NetworkInterface[] interfaces = NetworkInterface.GetAllNetworkInterfaces(); foreach (NetworkInterfac ...