网创优客建站品牌官网
为成都网站建设公司企业提供高品质网站建设
热线:028-86922220
成都专业网站建设公司

定制建站费用3500元

符合中小企业对网站设计、功能常规化式的企业展示型网站建设

成都品牌网站建设

品牌网站建设费用6000元

本套餐主要针对企业品牌型网站、中高端设计、前端互动体验...

成都商城网站建设

商城网站建设费用8000元

商城网站建设因基本功能的需求不同费用上面也有很大的差别...

成都微信网站建设

手机微信网站建站3000元

手机微信网站开发、微信官网、微信商城网站...

建站知识

当前位置:首页 > 建站知识

python实现广度优先搜索过程解析-创新互联

广度优先搜索

网站建设哪家好,找创新互联!专注于网页设计、网站建设、微信开发、微信小程序、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了敦煌免费建站欢迎大家使用!

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


复杂度: 时间复杂度为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")

网站题目:python实现广度优先搜索过程解析-创新互联
文章URL:http://bjjierui.cn/article/depeoc.html

其他资讯