酷站(www.ku0.com)-致力于为互联网从业者提供动力!

热门关键词:  企业  baidu  as  c4rp3nt3r  美女
酷站

python

旗下栏目: vbs hta htc perl DOS/BAT python VBA ColdFusion autoit PowerShell seraphzone linux shell Lua Golang Erlang ruby 游戏 远程脚本

python实现广度优先搜索的方法

来源:互联网搜集 作者:秩名 人气: 发布时间:2019-10-19
本篇文章主要介绍了python实现广度优先搜索的方法,对大家的学习或者工作具有一定的参考学习价值,感兴趣的小伙伴们可以参考一下,也感谢大家对酷站(ku0.com)的支持。

广度优先搜索

适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快

复杂度: 时间复杂度为O(V+E),V为顶点数,E为边数

思路

广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索;

代码
 

from collections import deque
 
#解决从你的人际关系网中找到芒果销售商的问题
#使用字典表示映射关系
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"] = []
 
#判断是否是要查找的目标 
def is_target_node(name):
   return name[-1] == 'm'
 
#实现广度优先搜索算法 
def search(name):
   search_queue = deque() #创建一个队列
   search_queue += graph[name] 
   searched = [] #记录用于检查过的人
   while search_queue: #只要队列不为空
     person = search_queue.popleft() #就取出其中的第一个人
     if not person in searched: #这个人没有被检查过
       if is_target_node(person): #判断这个人是否是要查找的销售商
         print(person + " is target node!")
         return True
       else:
         search_queue += graph[person] #如果这个人不是,就将这个人的朋友压入队列
         searched.append(person) #将这个人追加到已检查过的字典中
   return False
 
#调用方法
search("you")
 

原文链接:https://www.cnblogs.com/lty-fly/p/11699897.html

最新更新