广度优先搜索

图是什么?

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

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

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

image.png
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()
© 版权声明
THE END
喜欢就支持以下吧
点赞0
分享
评论 抢沙发
四曲的头像-四曲博客

昵称

取消
昵称表情代码图片