广度优先搜索
(breadth-first search,BFS)是一种图算法，能找出两样东西之间的最短距离。
最短路径问题，比如乘车去某个地点，中间需要换乘，路线有很多种，但总存在一条换乘最少的，最短路径。
基本概念
图
图由节点(node)、边(edge)组成。
在图中相互连接的节点被称为邻居。
广度优先搜索
这种算法用来解决2类问题：
- 是否存在路径
- 哪条路径最短
队列
在广度优先搜索中，搜索范围从起点向外延伸，但是对于数据需要按添加顺序查找。于是需要用到队列(queue)这一数据结构
队列(First in First Out,FIFO),先进先出；栈(Last In First Out,LIFO).
有向图(directed graph),有箭头指向；对应无向图(undirected graph)
算法原理
1.创建一个队列，用于存储数据
2.从队列中弹出一个数据，检查是否符合搜索条件
3.如果不符合条件则将该数据的所有邻居都加入队列，然后重复2
4.当队列为空，说明找不到符合条件的结果
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 search(name):
search_queue = deque()
search_queue +=graph[name]
searched = []
#条件列表不为空
while search_queue:
#从队列取第一个值
person = search_queue.popleft()
if not person in searched:
if person_is_seller(person):
print(person+' is a mango seller!')
return True
else:
#将该元素的邻居加入队列
search_queue += graph[person]
searched.append(person)
return False
def person_is_seller(name):
#假设的芒果商选择依据，名字末尾以m结尾
return name[-1] =='m'
该算法运行时间是由边数和人数决定的。O(V+E)，vertice and egde
拓扑排序
A依赖于B，在列表中A必须在B之后，是一个有序列表。
树图
需要补充
参考
《算法图解》
