一、广度优先搜索
广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。
广度优先搜索是一种用于图的查找方法，可以帮助解决两个问题：
从节点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.未搜索的邻居加入待搜索队列,注意需要满足两个条件才能加入带搜索队列将搜索完成的节点加入搜索完成节点集合不断循环直到找到目标节点或者待搜索队列为空Python实现代码：
from collections import dequedef 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 Trueelif (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='你')'''输出如下：{'你': ['刘备', '曹操', '孙权'], '刘备': ['诸葛亮', '法正'], '曹操': ['郭嘉', '荀彧', '关羽'], '孙权': ['周瑜', '鲁肃'], '诸葛亮': ['关羽']}找到了鲁肃'''
广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一。他的计算过程并不复杂，就像是剥洋葱，一层一层的寻找直到找到目标
