图解算法—广度优先搜索

文章目录

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

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

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

第一类问题

假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。为此，你可以在朋友及朋友的朋友中查找。

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

第二类问题

谁是关系最近的芒果销售商。例如，朋友是一度关系，朋友的朋友是二度关系。

在你看来，一度关系胜过二度关系，二度关系胜过三度关系，以此类推。因此，你应先在一度关系中搜索，确定其中没有芒果供应商后，才在二度关系中搜索。广度优先搜索就是这样做的，在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。所以，广度优先搜索不仅查找从A到B的路径，而且找到的是最短的路径。

注：在广度优先搜索中只有按添加顺序查找，才能实现这样的目的，所以广度优先搜索需要用到队列（先进先出，First In First Out）。

Python实现广度优先搜索

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

1）找到一位芒果供应商；

2）队列变成空的，这意味着你的人际关系网中没有芒果供应商。

from collections import deque

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 person_is_seller(name):
    return name[-1] == 'm'

def search_bfs(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("{} is a mango seller!".format(person))
                return True
            else:
                ## 不是芒果供应商，将这个人的朋友都加入搜索列表
                search_queue += graph[person]  
                searched.append(person)  ## 将这个人标记为检查过
    return False  ## 如果到达了这里，就说明队列中没人是芒果供应商

search_bfs("you")    

thom is a mango seller!
True

时间复杂度

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

小结

1）广度优先搜索指出是否有从A到B的路径；

2）如果有，广度优先搜索将找出最短路径；

3）面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题；

4）在广度优先搜索中，需要按加入顺序检查搜索列表中的节点，否则找到的就不是最短路径，因此搜索列表必须是队列（先进先出）；

5）对于检查过的节点，务必不要再去检查，否则可能导致无限循环。