广度优先搜索

发表于 分类于 ， 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 5 分钟
  • 学习使用新的数据结构图来建立网络模型。
  • 学习广度优先搜索，你可对图使用这种算法回答诸如“到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）的。
  • 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
  • 对于检查过的人，务必不要再去检查，否则可能导致无限循环。

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