广度优先搜索

  • 学习使用新的数据结构图来建立网络模型。
  • 学习广度优先搜索,你可对图使用这种算法回答诸如“到X的最短路径是什么”等问题。
  • 学习有向图和无向图。
  • 学习拓扑排序,这种排序算法指出了节点之间的依赖关系。

图简介

假设你居住在旧金山,要从双子峰前往金门大桥。你想乘公交车前往,并希望换乘最少。可乘坐的公交车如下。

20220615215302

为找出换乘最少的乘车路线,你将使用什么样的算法?

你经常要找出最短路径,这可能是前往朋友家的最短路径,也可能是国际象棋中把对方将死的最少步数。解决最短路径问题的算法被称为广度优先搜索。

  1. 使用图来建立问题模型。
  2. 使用广度优先搜索解决问题。

图是什么

图模拟一组连接。例如,假设你与朋友玩牌,并要模拟谁欠谁钱

20220615215704

图由节点(node)和边(edge)组成。一个节点可能与众多节点直接相连,这些节点被称为邻居。

图用于模拟不同的东西是如何相连的。

广度优先搜索

广度优先搜索是一种用于图的查找算法,可帮助回答两类问题。 第一类问题:从节点A出发,有前往节点B的路径吗? 第二类问题:从节点A出发,前往节点B的哪条路径最短?

查找最短路径

假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。朋友是一度关系,朋友的朋友是二度关系。

20220615215946

在你看来,一度关系胜过二度关系,二度关系胜过三度关系,以此类推。因此,你应先在一度关系中搜索,确定其中没有芒果销售商后,才在二度关系中搜索。广度优先搜索就是这样做的!

你按顺序依次检查名单中的每个人,看看他是否是芒果销售商。这将先在一度关系中查找,再在二度关系中查找,因此找到的是关系最近的芒果销售商。广度优先搜索不仅查找从A到B的路径,而且找到的是最短的路径。

注意,只有按添加顺序查找时,才能实现这样的目的。因此,你需要按添加顺序进行检查。有一个可实现这种目的的数据结构,那就是队列(queue)。

队列

队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队,如果你排在他前面,你将先上车。队列的工作原理与此相同。队列类似于栈,你不能随机地访问队列中的元素。队列只支持两种操作:入队和出队。

20220615220321

队列是一种先进先出(First In First Out,FIFO)的数据结构,而栈是一种后进先出(Last In First Out,LIFO)的数据结构。

实现图

每个节点都与邻近节点相连,如果表示类似于“你→Bob”这样的关系呢?好在你知道的一种结构让你能够表示这种关系,它就是散列表!散列表让你能够将键映射到值。在这里,你要将节点映射到其所有邻居。散列表是无序的,因此添加键—值对的顺序无关紧要。

Anuj、Peggy、Thom和Jonny都没有邻居,这是因为虽然有指向他们的箭头,但没有从他们出发指向其他人的箭头。这被称为有向图(directed graph),其中的关系是单向的。无向图(undirected graph)没有箭头,直接相连的节点互为邻居。

实现算法

20220615220736

这个算法将不断执行,直到满足以下条件之一:

  • 找到一位芒果销售商;
  • 队列变成空的,这意味着你的人际关系网中没有芒果销售商。

Peggy既是Alice的朋友又是Bob的朋友,因此她将被加入队列两次:一次是在添加Alice的朋友时,另一次是在添加Bob的朋友时。因此,搜索队列将包含两个Peggy。

因此,检查完一个人后,应将其标记为已检查,且不再检查他。如果不这样做,就可能会导致无限循环。为此,你可使用一个列表来记录检查过的人。

def search(name):
search_queue = deque()
search_queue += graph[name]
searched = [] ←------------------------------这个数组用于记录检查过的人
while search_queue:
person = search_queue.popleft()
if person not in searched: ←----------仅当这个人没检查过时才检查
if person_is_seller(person):
print person + " is a mango seller!"
return True
else:
search_queue += graph[person]
searched.append(person) ←------将这个人标记为检查过
return False

运行时间

如果你在你的整个人际关系网中搜索芒果销售商,就意味着你将沿每条边前行(记住,边是从一个人到另一个人的箭头或连接),因此运行时间至少为O(边数)。 你还使用了一个队列,其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的,即为O(1),因此对每个人都这样做需要的总时间为O(人数)。 所以,广度优先搜索的运行时间为O(人数 + 边数),这通常写作O(V + E),其中V 为顶点(vertice)数,E 为边数。

小结

  • 广度优先搜索指出是否有从A到B的路径。
  • 如果有,广度优先搜索将找出最短路径
  • 面临类似于寻找最短路径的问题时,可尝试使用图来建立模型,再使用广度优先搜索来解决问题。
  • 有向图中的边为箭头,箭头的方向指定了关系的方向,例如,rama→adit表示rama欠adit钱。
  • 无向图中的边不带箭头,其中的关系是双向的,例如,ross - rachel表示“ross与rachel约会,而rachel也与ross约会”。
  • 队列是先进先出(FIFO)的。
  • 栈是后进先出(LIFO)的。
  • 你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径,因此搜索列表必须是队列。
  • 对于检查过的人,务必不要再去检查,否则可能导致无限循环。

如果你在哪儿卡住了,可以到这里查看源码。