广度优先算法

本章内容

1. 学习使用新的数据结构来建立网络模型
2. 实习广度优先搜索，你可对图是用这种算法回答诸如“到X的最短路径是什么”等问题；
3. 学习有向图和无向图
4. 学习拓扑排序，这种排序算法指出了节点之间的依赖关系

解决最短路径问题的算法被称为广度优先算法（breadth-first search, BFS）

图示由节点（node）和边（edge）组成

查找最短路径问题：

广度优先搜索回答两类问题：

1. 第一类问题：从节点A出发，有前往节点B的路径吗？（在你的人际关系网中，有芒果销售商吗？）
2. 第二类问题：从节点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）
• 你需要按加入顺序检查搜素列表中的人，否则找到的就不是最短路径，因此搜素列表必须是队列；
• 对于检查过的人，务必不要再去检查，否则可能导致无限循环；