广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。
广度优先搜索是一种用于图的查找方法，可以帮助解决两个问题：
- 从节点A出发，有前往B节点的路径码？
- 从节点A出发，前往B节点的最短路径？
二、图的表示Python 1.先介绍下图结构
- 图模拟不同东西是如何相连的。
- 图由节点（node）和边（edge)组成
- 一个节点可能与众多节点直接相连，这些节点被称为邻居（neighbor）
如图：
图模拟不同东西是如何相连的。
图由节点（node）和边（edge)组成,
一个节点可能与众多节点直接相连，这些节点被称为邻居（neighbor）
2.图的Python实现我们使用散列表数据结构实现，在Python中字典（dict）是最常用的散列表。
散列表是无序的所以，字典中节点的添加是没有时序的，先添加和后添加并没有区别。
我们将上图用代码实现
graph={}
graph['你']=['刘备','曹操','孙权']
graph['刘备']=['诸葛亮','法正']
graph['曹操']=['郭嘉','荀彧','关羽']
graph['孙权']=['周瑜','鲁肃']
graph['诸葛亮']=['关羽']
print(graph)
'''
输入如下：
{'你': ['刘备', '曹操', '孙权'], '刘备': ['诸葛亮', '法正'], '曹操': ['郭嘉', '荀彧', '关羽'], '孙权': ['周瑜', '鲁肃'], '诸葛亮': ['关羽']}
'''
3.有向图和无向图
虽然有箭头指向节点’诸葛亮‘，但是没有从他出发的箭头，这被称为有向图。因此’诸葛亮‘是刘备的邻居，但刘备不是诸葛亮的邻居。
无向图没有箭头，直接相连的节点互为邻居。
三、广度优先算法原理及Python实现代码 广度优先搜索算法步骤
- 使用一个辅助队列 q，首先将出发节点 v 入队，将其标记为已访问，然后循环检测队列是否为空。
- 如果队列不为空，则取出队列第一个元素，并将与该元素相关联的所有未被访问的节点入队，将这些节点标记为已访问。
- 如果队列为空，则说明已经按照广度优先遍历了所有的节点。
算法原理图解
- 建立待搜索队列和搜索完成节点集合，将初始节点加入待搜索队列
- 对初始节点进行搜索，查看邻居是否为目标节点，
- 并将1.有子节点且2.未搜索的邻居加入待搜索队列,注意需要满足两个条件才能加入带搜索队列
- 将搜索完成的节点加入搜索完成节点集合
- 不断循环直到找到目标节点或者待搜索队列为空
from collections import deque
def BFSearch(graph,target,start_node):
# 辅助队列，用于存储待检查的节点
search_queue=deque()
search_queue.append(start_node)
# 检查过节点，集合，用于避免一个节点是另外多个节点邻居时，造成的重复检查
searched_set=set()
# 只要还有未检查的数据，就循环
while search_queue:
# 弹出最先加入的节点
node=search_queue.popleft()
# 将节点邻居取出来
for neighbor in graph[node]:
# 判断是否为 目标节点
if neighbor ==target:
print('找到了{}'.format(target))
return True
elif (neighbor in graph.keys()) and (neighbor not in searched_set):
# 不是目标节点，判断加入搜索队列的两个条件
# 1.自身为系欸但
# 2.未检查过
search_queue.append(neighbor)
searched_set.add(node)
print('没有找到')
return False
看一下运行结果
if __name__=='__main__':
graph={}
graph['你']=['刘备','曹操','孙权']
graph['刘备']=['诸葛亮','法正']
graph['曹操']=['郭嘉','荀彧','关羽']
graph['孙权']=['周瑜','鲁肃']
graph['诸葛亮']=['关羽']
print(graph)
BFSearch(graph,target='鲁肃',start_node='你')
'''
输出如下：
{'你': ['刘备', '曹操', '孙权'], '刘备': ['诸葛亮', '法正'], '曹操': ['郭嘉', '荀彧', '关羽'], '孙权': ['周瑜', '鲁肃'], '诸葛亮': ['关羽']}
找到了鲁肃
'''
广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一。他的计算过程并不复杂，就像是剥洋葱，一层一层的寻找直到找到目标
