广度优先搜索

图是什么？

图由边和节点构成，一个节点可能会与众多节点进行连接，这些节点成为邻居

在许多的编程语言当中，都提供了散列表的数据结构，借用散列表，我们可以具体来实现图结构的模拟

在Python当中，我们可以使用字典的方式来实现散列表，对于上述关系来说，我们可以这样来实现

grap["you"] = ['BOB',"ALICE",'CLAIRE']
grap["BOB"] = ['ANUJ','PEGGY']
grap['CLAIRE'] = ['THOM','JONNY']
grap['ALICE'] =['PEGGY']
grap['PEGGY'] = []
grap['ANUJ'] = []
grap['THOM'] = []
grap['JONNY'] = []

什么是广度优先搜索

广度优先搜索是一种用于图的搜索算法，主要解决以下两类问题

• 从A节点出发，是否能够达到B节点
• 从A节点出发，到达B节点的最短路径是什么

一度关系和二度关系

对你来说，你的朋友是一度关系，而你的朋友的朋友则是二度关系

过程

按照顺序，进行名单检查，先在一度关系中进行查找，然后在二度关系中进行查找，因此找到的是关系最近的那个你需要的人

在这里例子当中，我们想要找的是名称开头为T的那个人

注意 ：每一个已经扫描过的人需要做一次记录，否则可能会陷入在查找的死循环当中

队列

由于我们要先查找一度关系的人，然后在查找二度关系的人，这是有一定顺序在的，在这个顺序中，队列的数据结构刚好符合我们的需要，队列是一种先进先出 的数据结构，与栈不同，栈是一种先进后出 的结构

在Python当中，我们可以利用队列的数据结构来进行模拟

from collections import deque
quees = deque()    #新建一个数据队列
quees += "a"       #在队列当中加入内容
quees.popleft()    #弹出队首元素

代码实现

#新建图示
from collections import deque
​
grap = {}
​
grap["you"] = ['BOB',"ALICE",'CLAIRE']
grap["BOB"] = ['ANUJ','PEGGY']
grap['CLAIRE'] = ['THOM','JONNY']
grap['ALICE'] =['PEGGY']
grap['PEGGY'] = []
grap['ANUJ'] = []
grap['THOM'] = []
grap['JONNY'] = []
​
quees = deque()
​
def check_person(name):
    if name[0] == "P":
        return True
    else:
        return False
​
def main():
    quees = deque()
    quees += grap["you"]
    flag = []
    result = ""
    while quees:  #如果队列为空，则退出循环
        person = quees.popleft()  #弹出队首元素
        if not person in flag:  #没有查过的人才需要查询
            if check_person(person):  #检查是否是我们要的人
                result = person  #如果是，则退出循环
                break
            else:    #不是，则添加这个朋友的朋友，搜索二度关系
                quees += grap[person]
                flag.append(person)  #标记已经查询过了
​
    #输出最后结果
    if result == "":
        print("没有找到")
    else:
        print(result)
​
main()