【算法图解】广度优先搜索

广度优先搜索

广度优先搜索可以回答两类问题：

1. 从节点A出发，有前往节点B的路径吗？
2. 从节点A出发，前往节点B哪条路径最短？

算法原理

广度优先算法通过队列来实现，队列是一种先进先出结构。具体操作如下：

1. 先将图用散列表表示
2. 创建队列，将所有邻居都加入到队列当中。
3. 从第一层邻居关系开始搜索，直到所有邻居都搜索完。
4. 返回结果

代码表现

# coding: utf-8
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 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

def person_is_seller(name):
    return name[-1] == 'm'

search("you")

运行时间

广度优先沿着每条边前行，然后将每个人加入队列中检查，所以运行时间为O(边数+人数)，通常写做O(V+E)。