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

Python  /  管理员 发布于 7年前   133

广度优先搜索

适用范围： 无权重的图，与深度优先搜索相比，深度优先搜索法占内存少但速度较慢，广度优先搜索算法占内存多但速度较快

复杂度： 时间复杂度为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")

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