广度优先搜索算法

什么是广度优先搜索？

广度优先搜索让你能够找出两样东西之间的最短距离

使用场景

• 跳棋AI，计算最少走多少步获胜
• 单词拼写检查器，计算最少编辑多少个地方可以将单词拼对
• 根据人际关系网找到关系最近的医生
• 等

什么是图？

just画一个金沙湖到西湖的路线图
图由节点和边组成
时间复杂度 O(V+E)

案例

(1)问题描述

找出关系最近的芒果经销商

(2)实现算法
<1> 创建一个队列，用于存储需要检查的人
<2> 从队列中弹出一个人
<3> 检查这个人是不是芒果经销商(如果是,大功告成，如果否则将这个人所有邻居加入队列)
<4> 回到第二步
<5> 如果队列为空，就说明你的人际关系网中没有卖芒果的

(3) 代码

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["you"]
    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]
    return False

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

search("you")

(4)两个问题
<1> 为什么要使用队列？
<2> 如果不加searched会怎么样？