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中字典的基本知识初步介绍

 字典是可变的,并且可以存储任意数量的Python对象,包括其他容器类型另一个容器类型。字典包括键对(称为项目)及其相应的值。 Python字典也被称为关联数组或哈希表。字典的...

Python给图像添加噪声具体操作

Python给图像添加噪声具体操作

在我们进行图像数据实验的时候往往需要给图像添加相应的噪声,那么该怎么添加呢,下面给出具体得操作方法。 1、打开Python的shell界面,界面如图所示; 2、载入skimage工具包...

PYTHON压平嵌套列表的简单实现

list 是 Python 中使用最频繁的数据类型, 标准库里面有丰富的函数可以使用。 不过,如果把多维列表转换成一维列表(不知道这种需求多不多),还真不容易找到好用的函数, 要知道...

numpy按列连接两个维数不同的数组方式

合并两个维数不同的ndarray 假设我们有一个3×2 numpy数组: x = array(([[1,2], [3, 4], [5,6]])) 现在需要把它与一个一维数组:...

Python实现简单HTML表格解析的方法

本文实例讲述了Python实现简单HTML表格解析的方法。分享给大家供大家参考。具体分析如下: 这里依赖libxml2dom,确保首先安装!导入到你的脚步并调用parse_tables(...