python实现广度优先搜索过程解析

yipeiwu_com5年前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设计】。

相关文章

python实现bitmap数据结构详解

python实现bitmap数据结构详解

bitmap是很常用的数据结构,比如用于Bloom Filter中;用于无重复整数的排序等等。bitmap通常基于数组来实现,数组中每个元素可以看成是一系列二进制数,所有元素组成更大的二...

python-tornado的接口用swagger进行包装的实例

python-tornado的接口用swagger进行包装的实例

写这个文章的主要原因,就是因为没有相关的东西,导致我完全不知道应该怎么做,经过了两个晚上的摸索,终于搞清楚了,如果有谁需要tornado+swagger的输出模式,可以照这个套; 主要是...

用openCV和Python 实现图片对比,并标识出不同点的方式

用openCV和Python 实现图片对比,并标识出不同点的方式

最近项目中需要实现两组图片对比,并能将两者的区别标识出来。 在网上搜索一大堆找到一篇大神的文章,最终实现该功能,在这里记录下: 想要实现此demo,首先我们得确保电脑上已安装 openC...

Django URL传递参数的方法总结

1 无参数情况 配置URL及其视图如下: (r'^hello/$', hello) def hello(request): return HttpResponse("Hell...

Django ORM多对多查询方法(自定义第三张表&ManyToManyField)

对于多对多表 - 1.自定义第三张表,更加灵活 - 2.ManyToManyField 自动生成第3张表 只能 有3列数据 不能自己添加。 自定义第三张表 # models.py...