广度优先搜索（breadth-first search，BFS）

最短路径问题（shortest-path-problem），例如

• 编写国际跳棋AI，计算最小走多少步就可以获胜；
• 编写拼写检查器，计算最少编辑多少个地方就可以将错拼的单词改造成正确的单词，如将READED改为READER需要编辑一个地方；
• 根据你的人际关系网络找到关系最近的医生。

解决最短路径问题的算法，被称为广度优先搜索

实现广度优先搜索的步骤

1. 使用图来建立问题模型
2. 使用广度优先搜索解决问题

图

图由节点和边组成。相连的节点称为邻居，比如b是a的邻居，c是b的邻居，a是c的邻居。

图.jpg

可以使用散列表（key/value）实现图，模拟节点到它的邻居的映射关系，key为节点，value为节点的所有邻居节点组成的数组，例如：

graph = {} #散列表（键值对）
graph["a"] = ["b"] # b是a的邻居
graph["b"] = ["c"] # c是b的邻居
graph["c"] = ["a"] # a是c的邻居

队列

队列是一种先进先出（First In First Out，FIFO）的数据结构。

实现广度优先算法

比如，你的人际关系网如下
你的朋友（Alice，Bob，Claire）与你关系最近，称为一度关系
你朋友的朋友（Alice的朋友Peggy）为二度关系
在与你最近的关系中找到名字以“m”结尾的人

你的人际关系网.png

算法思路
1、你的关系网中是否存在名字以“m”结尾的人
首先查找你所有的朋友
如果找到，返回；
如果没有，将你朋友的朋友加入查找队列
2、如果存在，在其中找出与你关系最近的人
应首先在你的朋友（一度关系）中查找：先将所有一度关系加入队列
如果没有，才在你朋友的朋友（二度关系）中查找，再将所有二度关系加入队列
查找时，从队列中依次取出
3、去重
查找时，应判断此人是否已被检查过，如果不判断，那么下面的关系将导致算法死循环

graph = {}
graph["a"] = ["b"]
graph["b"] = ["a"]

算法实现

# 姓名以m结尾的人
def person_is_seller(name):
    return name[-1] == '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"] = []

# 创建队列
# 从队列中依次检查每个人
# 首先判断此人是否已被检查过
# 如果没有，判断此人姓名是否以m结尾。如果是，返回结果；如果不是，将此人的朋友加入队列
from collections import deque
def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if not person in searched:
            if person_is_seller(person):
                print(person + " ’s name is end with m")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False

search("you")