理解广度优先搜索

简单的例子来理解广度优先搜索

广度优先搜索是一种图查找算法，简要介绍图的概念：

假设你与一群朋友玩牌，并模拟谁欠谁的钱，完整的欠钱图类似下面这样：

小明欠小红的钱，小红欠梅梅的钱，依次类推。图由节点和边组成，比如小明、小红…这几个圆圈就是节点，节点之间就是边，一个节点可能与众多节点直接相连，这些节点称为邻居，比如梅梅既是小红的邻居，也是李雷的邻居。

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

第一类问题： 从节点小明出发，有没有前往节点梅梅的路径
第二类问题： 从节点小明出发，前往节点梅梅的哪条路径最短

争对第一类问题，举例如下（最近看了发哥的赌神）：

假设你想要拜赌神为师，于是你发动所有朋友的力量来寻找赌神，首先创建一个朋友名单，然后对名单中每个人依次检查，看他是否为赌神。假设你的朋友中没有赌神，就从朋友的朋友中查找。检查名单中每个人时，都将其朋友加入名单。利用这种算法将搜遍你的人际关系网，直到找到赌神，这就是广度优先搜索算法。
但是这样只是回答了第一类问题，为了找到最短路径，我们需要用到一种数据结构——队列。
你可以把队列想象成一群人在排队上公交车，排在前面的先上车，即先进先出，队列的操作有入队和出队两种操作。利用队列来实现广度优先搜索。
队列
另外，为了实现图，我们还需要用到散列表结构，即Python中的字典结构，可以用来表示人物关系，类似于“你——>赌神”这种。

graph={}
graph['你']=['小明','小方','梅梅']
graph['梅梅']=['赌神']
graph['小红']=['周杰伦','赌神']
graph['小明']=['刘德华','周星星']
graph['周杰伦']=[]
graph['赌神']=[]
graph['刘德华']=[]
graph['周星星']=[]

于是，“你”被映射到了一个数组，其中包含了“你”的所有邻居

以上图中有箭头指向，被称为有向图，用来表示你的人际关系网。
下面步入整体，对算法进行具体实现，首先概述工作原理：

详细代码如下：

from collections import deque

def person_is_GamblerGad(name):
    return name=='赌神'
def search(name):
    search_deque = deque()  # 创建搜索队列
    search_deque += graph['你']  # 将你的朋友加入队列
    searched = []  # 用来存储检查过的人
    while search_deque: # 只要队列不为空
        person=search_deque.popleft()  # 每次检查队列的第一个人
        if person not in searched:
            if person_is_GamblerGad(person): # 检查他是不是赌神
                print(person+"我要拜你为师！")
                return True
            else:
                search_deque+=graph[person]
                searched.append(person)
    return False
search('你')

代码结束条件为：①找到了“赌神”②队列为空，即你的人际关系网中没有“赌神”。
输出结果：

假设你在人际网中搜索“赌神”，其时间复杂度为O（V）+O（E），V为顶点数，E为边数，即你要沿每条边前进搜索，花费为O（V），另外使用了一个队列要检查每个人，对每个人进行检查时间是固定的，总共为O（E）。