实用宽度优先搜索实例 宽度优先搜索open表排序策略汇聚

网友 分享 时间:

【导读预览】此篇优秀范文“实用宽度优先搜索实例 宽度优先搜索open表排序策略汇聚”由阿拉题库网友为您整理分享,以供您参考学习之用,希望此篇资料对您有所帮助,喜欢就复制下载支持吧!

宽度优先搜索实例 宽度优先搜索open表排序策略篇1

宽度优先搜索又称广度优先搜索,简称bfs。下面网友为大家整理了(*),希望能帮到大家!

搜索的方式是:从一个点开始,逐层的遍历访问周围的点。比如有一个5*5的矩阵,每次可以访问某个点周围所有八个点,则如果从中心点开始宽度搜索,只需两层即可遍历完整个矩阵。

宽度搜索可用于对树、图、矩阵等进行搜索,适合用于求最短路径等问题。

算法关键词:队列,利用队列先进先出的`特点。队列中存储待遍历的点,如果队列不空,就从队列中取出第一个元素,将此元素标记为已访问,再把与这个元素相邻的未被标记的元素添加到队列末尾,循环直到队列变为空。从某个点开始搜索,只需要先把这个点添加到队列中,然后开始遍历的操作。

个人觉得宽度优先搜索还是很容易学的,因为它的思想容易理解,而且写的套路很固定。

实际应用:爬虫。爬虫一般是首先将几个母站添加到爬虫队列;然后从队列中取出要爬的网站,分析网页中包含的链接,将链接添加到爬虫队列,再爬取网站内容;不断往复这个操作,这和宽度搜索的执行方式几乎是一样的。

下面做几道题来练习:

1、给一个01矩阵,求不同的岛屿的个数。0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

样例

[

[1, 1, 0, 0, 0],

[0, 1, 0, 0, 1],

[0, 0, 0, 1, 1],

[0, 0, 0, 0, 0],

[0, 0, 0, 0, 1]

]

上图矩阵有3个岛。

思路:遍历图,只要找到一个岛,就对这个岛进行宽搜,把和它相邻的所有岛都找出来并且标记,这样一个大岛就找到了。当整个图被遍历后,也就找到了所有大岛的个数。

2、给定一个矩阵,2代表墙,1代表僵尸,0代表人。僵尸每天可以将上下左右与之相邻的人咬成僵尸,但是僵尸不能穿墙。求将所有的人变为僵尸需要几天,如果不能全部变为僵尸返回-1.

0 1 2 0 0

1 0 0 2 1

0 1 0 0 0

思路:首先我们应该统计出当前的人数,然后将图中所有僵尸坐标加入队列,对队列中的点进行搜索,每遍历一层增加一天(很重要),搜索过程中遇到人就将人数-1。最后看人数如果归零,证明全部变为僵尸,返回天数,否则返回-1.

s("content_relate");

php算法学习之宽度优先搜索相关文章:

php算法学习之动态规划

11-11

php学习之php配置

09-10

php红包算法

11-08

php算法学习之分治法

11-13

php学习之php预定义变量

10-04

php经典算法题

11-06

php经典算法介绍

08-21

php排序算法类讲解

11-23

php可逆加密解密算法

11-10

48 1373912
");