广度优先搜索是什么（广度优先搜索是什么搜索）



假如你现在位于双子峰，要到金门大桥。设定从一个地点到其相邻的一个地点需要一步，那么你到金门大桥最少要多少步？

我们会怎么想呢？我们肯定会先想，一步行不行，即一步能不能到目的地——有没有一步就到目的地的路——在每个出发地到其相邻地点的路中确认。发现显然不行，那我们又看有没有只再进一步就到目的地的路，确认每一条······这样确认下去直到有想要的结果。

上述地图是一个图（graph）模型。就像雷达逐距离扫描一样，我们的想法就是所谓广度（宽度）优先搜索：

算法首先检查和起点距离为k的所有顶点，若不能达到要求，再去检查和S距离为k+l(l>0)的其他顶点。

显然，广度优先搜索找到的是距起点最近的目标。具体地说，在上述金门大桥的案例中，该算法找到的是可达的最短路径——找到它的同时也解决了存不存在到达那里的路径的问题。

而如果不能由BFS找到到达的路径（层层扫描，直到最后都没有找到能够到达的），那么结果就是不存在到达的路径。

综上所述，BFS找不到路径，那么就不存在到达的路径；BFS找到了路径，那就表明存在到达的路径，也找到了其中最短的。

因此，BFS解决的是这两个问题：存不存在到达的路径，和，最短的到达路径是什么。

假设你经营着一个芒果农场，需要寻找芒果销售商将芒果卖给他。你想在社交网络上找，而且要关系尽量不疏远。

解决：

要关系尽量不疏远，显然这是一个最短到达问题。首先，你在联系人列表中查找；发现没有一个满足，你再在联系人的联系人中找；发现又没有一个满足，你再在联系人的联系人的联系人中找；······直到找到或终究没找到。

顾名思义，队列就是我们生活中排的那种队。比如一群人到银行的同一个柜台办理业务，那么先到先办，排列成队。这就是一个“先进先出”。

因此，我们的办法就是一层关系一层关系的检查。那么如何表示每一层关系呢？

比如说，我的第一层联系人是：A, B,即 me: A, B;

那么我的第二层联系人就是这样：

A: E, F;         B: C, D;

后面层的联系人也是一样——

是的。另外，A是不是销售商，可以用0或1表示，它也是一个value。那么所有的这些键值对可以构成一个散列表（python中已有现成的散列表object：字典）。以人名为键，值为列表，列表的第一个元素为0或1，后面的元素为这个人的第一层联系人。

graph表示了这个关系图：

做法一：我们可以检查到一个人不是销售商时，就把他拥有的第一层关系加入检查序列。检查序列自始至终都是一个队列，变的是队列的元素，直接使用队列结构就行。

代码：

做法二：

事实上我们更容易直接地想到，。

也就是说我们不必要用到队列也可以解决问题。

代码：

这两种办法的性能应该没有多少差别。不过实测发现好像做法二快一点点——

据说，set()操作去重是更快的办法。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/59044.html