首页 ›存档› 技术 › 查看内容

php算法学习之宽度优先搜索

2018-3-30 13:00 |来自: 互联网 353 0

摘要: 宽度优先搜索又称广度优先搜索，简称bfs。搜索的方式是：从一个点开始，逐层的遍历访问周围的点。比如有一个5*5的矩阵，每次可以访问某个点周围所有八个点，则如果从中心点开始宽度搜索，只需两层即可遍历完整个矩 ...

宽度优先搜索又称广度优先搜索，简称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.

--------------伟大的分割线----------------

PHP饭米粒(phpfamily) 由一群靠谱的人建立，愿为PHPer带来一些值得细细品味的精神食粮！

饭米粒只发原创或授权发表的文章，不转载网上的文章

所发的文章，均可找到原作者进行沟通。

也希望各位多多打赏（算作稿费给文章作者），更希望大家多多投搞。

投稿请联系：

[email protected]

本文由 ShutLove 向饭米粒投稿，转载请注明本来源信息和以下的二维码（长按可识别二维码关注）

本文转载于微信公众号: PHP饭米粒(phpfamily)，更多微信文章请扫描关注公众号:

声明：文章版权归原作者所有部分文章转自互联网如有侵权请联系 [邮箱地址] 删除