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

 更新时间:2019年10月19日 10:34:23   作者:水滴月   我要评论
这篇文章主要介绍了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")

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

相关文章

  • 深入浅析Python2.x和3.x版本的主要区别

    深入浅析Python2.x和3.x版本的主要区别

    这篇文章主要介绍了Python2.x和3.x版本的主要区别,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
    2018-11-11
  • Python XML转Json之XML2Dict的使用方法

    Python XML转Json之XML2Dict的使用方法

    今天小编就为大家分享一篇Python XML转Json之XML2Dict的使用方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2019-01-01
  • pandas如何处理缺失值

    pandas如何处理缺失值

    这篇文章主要介绍了pandas如何处理缺失值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
    2019-07-07
  • pytorch 模型可视化的例子

    pytorch 模型可视化的例子

    今天小编就为大家分享一篇pytorch 模型可视化的例子,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2019-08-08
  • 简单总结Python中序列与字典的相同和不同之处

    简单总结Python中序列与字典的相同和不同之处

    这篇文章主要介绍了Python中序列与字典的相同和不同之处,序列这里讲到Python中最常用的列表和元组以及字典三种,需要的朋友可以参考下
    2016-01-01
  • 解决Django中调用keras的模型出现的问题

    解决Django中调用keras的模型出现的问题

    今天小编就为大家分享一篇解决Django中调用keras的模型出现的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2019-08-08
  • python语言元素知识点详解

    python语言元素知识点详解

    在本篇文章中小编给大家分享了关于python语言元素的相关知识点以及实例代码,需要的朋友们跟着学习下。
    2019-05-05
  • 解决python删除文件的权限错误问题

    解决python删除文件的权限错误问题

    下面小编就为大家分享一篇解决python删除文件的权限错误问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-04-04
  • python 画三维图像 曲面图和散点图的示例

    python 画三维图像 曲面图和散点图的示例

    今天小编就为大家分享一篇python 画三维图像 曲面图和散点图的示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-12-12
  • python cookielib 登录人人网的实现代码

    python cookielib 登录人人网的实现代码

    今天晚上不是很忙,所以早早的就在电脑的旁边开始写东西了。我今天给大家分享一个我自己用python写的自动登录 人人网的脚本,没办法就是懒!懒的输入帐号和密码,让python给我们减少工作量
    2012-12-12

最新评论