【内部资料】广度优先搜索

。广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。

第一类问题：从节点A出发，有前往节点B的路径吗？

第二类问题：从节点A出发，前往节点B的哪条路径最短？

下面来详细地研究这个算法，你将使用它来回答第一类问题：有路径吗？

假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。在Facebook，你与 芒果销售商有联系吗？为此，你可在朋友中查找

这种查找很简单。首先，创建一个朋友名单

然后，依次检查名单中的每个人，看看他是否是芒果销售商。

假设你没有朋友是芒果销售商，那么你就必须在朋友的朋友中查找。

检查名单中的每个人时，你都将其朋友加入名单

这样一来，你不仅在朋友中查找，还在朋友的朋友中查找。别忘了，你的目标是在你的人际 关系网中找到一位芒果销售商。

因此，如果Alice不是芒果销售商，就将其朋友也加入到名单中。 这意味着你将在她的朋友、朋友的朋友等中查找。

使用这种算法将搜遍你的整个人际关系网，直 到找到芒果销售商。这就是广度优先搜索算法。

查找最短路径 再说一次，广度优先搜索可回答两类问题。 

 第一类问题：从节点A出发，有前往节点B的路径吗？（在你的人际关系网中，有芒果销 售商吗？） 

 第二类问题：从节点A出发，前往节点B的哪条路径最短？（哪个芒果销售商与你的关系最近？） 

刚才你看到了如何回答第一类问题，下面来尝试回答第二类问题——谁是关系最近的芒果销 售商。

例如，朋友是一度关系，朋友的朋友是二度关系。

在你看来，一度关系胜过二度关系，二度关系胜过三度关系，以此类推。

因此，你应先在一 度关系中搜索，确定其中没有芒果销售商后，才在二度关系中搜索。

广度优先搜索就是这样做的！ 在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查 二度关系。

顺便问一句：将先检查Claire还是Anuj呢？Claire是一度关系，而Anuj是二度关系，因 此将先检查Claire，后检查Anuj。 

你也可以这样看，一度关系在二度关系之前加入查找名单。 

你按顺序依次检查名单中的每个人，看看他是否是芒果销售商。这将先在一度关系中查找， 再在二度关系中查找，因此找到的是关系最近的芒果销售商。

广度优先搜索不仅查找从A到B的 路径，而且找到的是最短的路径。

注意，只有按添加顺序查找时，才能实现这样的目的。换句话说，如果Claire先于Anuj加入 名单，就需要先检查Claire，再检查Anuj。

如果Claire和Anuj都是芒果销售商，而你先检查Anuj 再检查Claire，结果将如何呢？

找到的芒果销售商并非是与你关系最近的，因为Anuj是你朋友的 朋友，而Claire是你的朋友。

因此，你需要按添加顺序进行检查。有一个可实现这种目的的数据 结构，那就是队列（queue）

实现算法 先概述一下这种算法的工作原理

运行时间 如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是 从一个人到另一个人的箭头或连接），

因此运行时间至少为O(边数)。 你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的， 即为O(1)，

因此对每个人都这样做需要的总时间为O(人数)。所以，广度优先搜索的运行时间为 O(人数 + 边数)，这通常写作O(V + E)，其中V为顶

点（vertice）数，E为边数

下面的小图说明了我早晨起床后要做的事情

该图指出，我不能没刷牙就吃早餐，因此“吃早餐”依赖于“刷牙”。 另一方面，洗澡不依赖于刷牙，因为我可以先洗澡再刷牙。

根据这个图，可创建一个列表， 指出我需要按什么顺序完成早晨起床后要做的事情

 (1) 起床

 (2) 洗澡

 (3) 刷牙

 (4) 吃早餐 

请注意，“洗澡”可随便移动，因此下面的列表也可行：

 (1) 起床 

(2) 刷牙 

(3) 洗澡 

(4) 吃早餐 

请问下面的三个列表哪些可行、哪些不可行？

下面是一个更大的图，请根据它创建一个可行的列表。

从某种程度上说，这种列表是有序的。如果任务A依赖于任务B，在列表中任务A就必须在任 务B后面。这被称为拓扑排序，

使用它可根据图创建一个有序列表。假设你正在规划一场婚 礼，并有一个很大的图，其中充斥着需要做的事情，但却不知道要从哪里开始。

这时就可使 用拓扑排序来创建一个有序的任务列表。

假设你有一个家谱

这是一个图，因为它由节点（人）和边组成。其中的边从一个节点指向其父母，但所有的边 都往下指。在家谱中，往上指的边不合情理！

因为你父亲不可能是你祖父的父亲

这种图被称为树。树是一种特殊的图，其中没有往后指的边。