广度优先搜索

应用场景

广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广 度优先搜索可以：

  1. 编写国际跳棋AI，计算最少走多少步就可获胜；

  2. 编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将 READED改为READER需要编辑一个地方；

  3. 根据你的人际关系网络找到关系最近的医生。

  4. 计算两地最短距离，这里的距离是指的路径段数而不是里程。

举例解释

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

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

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

假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。

你不仅在朋友中查找，还在朋友的朋友中查找。别忘了，你的目标是在你的人际 关系网中找到一位芒果销售商。因此，如果Alice不是芒果销售商，就将其朋友也加入到名单中。 这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个人际关系网，直 到找到芒果销售商。这就是广度优先搜索算法。

一度关系胜过二度关系，二度关系胜过三度关系，以此类推。因此，你应先在一 度关系中搜索，确定其中没有芒果销售商后，才在二度关系中搜索。广度优先搜索就是这样做的！ 在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。这能使你先找到关系最近的芒果销售商。

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

散列表是无序的，因此添加键—值对的 顺序无关紧要。对于检查过的人，务必不要再去检查，否则可能导致无限循环。

有向图无向图

Anuj、Peggy、Thom和Jonny都没有邻居，这是因为虽然有指向他们的箭头，但没有从他们 出发指向其他人的箭头。这被称为有向图（directed graph），其中的关系是单向的。因此，Anuj 是Bob的邻居，但Bob不是Anuj的邻居。无向图（undirected graph）没有箭头，直接相连的节点互 为邻居。例如，下面两个图是等价的。

在我所知道的算法中，图算法应该是最有用的。

Python代码实现：

找出关系最近的芒果销售商。

from collections import deque
#在Python中，可使用函数deque来创建一个双端队列。

def person_is_seller(name):
      return name[-1] == 'm'
      #这个函数检查人的姓名是否以m结尾：如果是，他就是芒果销售商。
      #为什么这么判断一个人是不是芒果销售商呢？就当题目默认的，
      #这是我们知道的芒果销售商的假定特征；

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
#键值对形式添加图，将节点映射到其所有邻居，图不过是一系列的节点和边

def search(name):
    search_queue = deque()#创建一个队列；
    search_queue += graph['you']#将你的邻居都加入到这个搜索队列中
    # This array is how you keep track of which people you've searched before.
    searched = []
    #这个数组用于记录检查过的人
    while search_queue:#只要队列不为空，
        person = search_queue.popleft()#就取出第一个人；同时队列变短。
        # Only search this person if you haven't already searched them.
        if not person in searched:
        #仅当这个人没检查过时才检查
            if person_is_seller(person):
                print (person + " is a mango seller!")
                return True
            else:
                search_queue += graph[person]
                #不是芒果销售商，将这个人的朋友都加入搜索队列；同时队列变长。
                # Marks this person as searched
                searched.append(person)
                #将这个人标记为检查过
    return False
    #如果到达了这里，就说明队列中没人是芒果销售商；

search("you")

输出：
thom is a mango seller!
#感觉还挺有意思的

运行时间

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

图(graph)由多个节点(vertex)构成，节点之间阔以互相连接组成一个网络。(x, y)表示一条边(edge)，它表示节点x与y相连。边可能会有权值(weight/cost)。

图分为两种:

  • 无向图

  • 有向图

在编程语言中，图有可能有以下两种形式表示：

  • 邻接矩阵(Adjacency Matrix)

  • 邻接表(Adjacency List)

遍历图有两种算法

  • 广度优先搜索(Breadth First Search)

  • 深度优先搜索(Depth First Search)

常见的图代码面试题

Previous二叉树Next狄克斯特拉算法

Last updated