Python实现广度优先搜索(BFS)算法详解

叶初

发布时间：2026-10-13| 6人浏览过

原创

本文解析Python中广度优先搜索(BFS)的实现原理。BFS适用于无权图，按层遍历节点，时间复杂度O(V+E)。通过Python队列(deque)和字典构建图结构，演示如何查找特定目标节点，并提供完整可运行代码示例。

广度优先搜索概述

广度优先搜索

适用场景与复杂度

适用场景：该算法主要用于无权重的图结构。与深度优先搜索相比，深度优先搜索占用内存较少但运行速度较慢，而广度优先搜索虽然占用内存较多，但搜索速度相对较快。

复杂度分析：算法的时间复杂度为O(V+E)，其中V代表图中的顶点数量，E代表边的数量。

算法核心思路

核心思路

广度优先搜索以层级为遍历顺序，即先搜索当前层的所有节点，待当前层节点全部处理完毕后，再向下一层继续搜索。

Python代码实现

代码实现


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")

以上即为本文的全部内容，希望上述解析对您的学习有所帮助，也欢迎大家继续支持本站获取更多技术资源。