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

yipeiwu_com7年前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以并发方式编写高性能端口扫描器的方法

关于端口扫描器 端口扫描工具(Port Scanner)指用于探测服务器或主机开放端口情况的工具。常被计算机管理员用于确认安全策略,同时被攻击者用于识别目标主机上的可运作的网络服务。 端...

用python写一个定时提醒程序的实现代码

用python写一个定时提醒程序的实现代码

身体是革命的本钱,身体健康了我们才有更多精力做自己想做的事情,追求女神,追求梦想。然而程序员是一个苦比的职业,大部分时间都对着电脑,我现在颈椎就不好了,有时候眼睛还疼,我还没20阿,伤心...

python网络编程学习笔记(六):Web客户端访问

6.1 最简单的爬虫 网络爬虫是一个自动提取网页的程序,它为搜索引擎从万维网上下载网页,是搜索引擎的重要组成。python的urllib\urllib2等模块很容易实现这一功能,下面的例...

python 按照固定长度分割字符串的方法小结

有如下的一堆mac地址,需要更改成一定格式,如mac='902B345FB021'改为mac='90-2B-34-5F-B0-21'。 借助python脚本,可以轻松实现,原理就是:字符...

python算法学习之基数排序实例

基数排序法又称桶子法(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其...