广度优先算法
2019-03-13 本文已影响0人
overad
本章内容
- 学习使用新的数据结构来建立网络模型
- 实习广度优先搜索，你可对图是用这种算法回答诸如“到X的最短路径是什么”等问题；
- 学习有向图和无向图
- 学习拓扑排序，这种排序算法指出了节点之间的依赖关系
解决最短路径问题的算法被称为广度优先算法（breadth-first search, BFS）
图示由节点（node）和边（edge）组成
查找最短路径问题：
广度优先搜索回答两类问题：
- 第一类问题：从节点A出发，有前往节点B的路径吗？（在你的人际关系网中，有芒果销售商吗？）
- 第二类问题：从节点A出发，前往节点B的哪条路径最短？（哪个芒果销售商与你的关系最近？）
队列：先进先出（First in First Out,FIFO）
栈：后进先出（Last In First Out,LIFO）
#广度优先算法
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"] = []
from collections import deque
# search_deque = deque() #创建一个队列
# search_deque += graph["you"]
def search(name):
search_deque = deque()
search_deque += graph[name]
searched = []
while search_deque:
person = search_deque.popleft()
if person not in searched:
if person_is_seller(person):
print(person + " is a mango seller！")
return True
else:
search_deque += graph[person]
searched.append(person)
return False
def person_is_seller(name):
if name[-1] == 'm':
return True
树是一种特殊的图：其中没有往后指的边；
如果任务A依赖于任务B，在列表中任务A就必须在任务B后面，这被称为拓扑排序；
小结：
- 广度优先搜索指出的是否有从A到B的路径；
- 如果有，广度优先搜素将找出最短路径；
- 面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜素来解决问题；
- 有向图中的边为箭头，箭头的方向表示了关系的方向，例如，rama->adit表示rama欠adit钱；
- 无向图中的边不带箭头，其中的关系是双向的；
- 队列是先进先出(FIFO)
- 栈是后进先出（LIFO）
- 你需要按加入顺序检查搜素列表中的人，否则找到的就不是最短路径，因此搜素列表必须是队列；
- 对于检查过的人，务必不要再去检查，否则可能导致无限循环；
