python实现广度优先搜索过程解析
广度优先搜索
适用范围:无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快
复杂度:时间复杂度为O(V+E),V为顶点数,E为边数
思路
广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索;
代码
fromcollectionsimportdeque #解决从你的人际关系网中找到芒果销售商的问题 #使用字典表示映射关系 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"]=[] #判断是否是要查找的目标 defis_target_node(name): returnname[-1]=='m' #实现广度优先搜索算法 defsearch(name): search_queue=deque()#创建一个队列 search_queue+=graph[name] searched=[]#记录用于检查过的人 whilesearch_queue:#只要队列不为空 person=search_queue.popleft()#就取出其中的第一个人 ifnotpersoninsearched:#这个人没有被检查过 ifis_target_node(person):#判断这个人是否是要查找的销售商 print(person+"istargetnode!") returnTrue else: search_queue+=graph[person]#如果这个人不是,就将这个人的朋友压入队列 searched.append(person)#将这个人追加到已检查过的字典中 returnFalse #调用方法 search("you")
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。