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

yipeiwu_com6年前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 Tcp协议发送和接收信息的例子

需要建立2个文件,一个作为客户端,一个作为服务端 文件一 作为客户端client,文件二作为服务端server 文件一 # client 客户端 # TCP必须建立连接 import...

利用python库在局域网内传输文件的方法

1.电脑已经搭建python环境 2.深入到需要传输的文件目录下,此处以分享 nemo-huiyuanfei 文件为例 3.在路径栏输入 cmd 按回车进入终端 4.输入命令 pytho...

简单的Python2.7编程初学经验总结

简单的Python2.7编程初学经验总结

如果你从来没有使用过Python,我强烈建议你阅读Python introduction,因为你需要知道基本的语法和类型。 包管理 Python世界最棒的地方之一,就是大量的第三方程序包...

浅谈numpy数组的几种排序方式

简单介绍 NumPy系统是Python的一种开源的数组计算扩展。这种工具可用来存储和处理大型矩阵,比Python自身的嵌套列表(nested list structure)结构要高效的多...

解决Atom安装Hydrogen无法运行python3的问题

解决Atom安装Hydrogen无法运行python3的问题

Atom是一款功能强大的跨平台编辑器,插件化的解决方案为atom社区的繁荣奠定了基础。任何人都可以把自己做的组件贡献在github上,并能方便的安装到Atom上使用。 Jupyter N...