7 狄克斯特拉算法（带权的最短路径，地图路线中的算法）有点没看明白，下期整理。
6 广度优先搜索
广度优先搜索（breadth-first search，BFS）解决等权重中路径选择的问题，类似于有多条公交线路可选时，如何找到站数（只管站数，不管站间权重）最少的路线。
算法的核心过程：基于图，一级一级的做遍历：
- step1 从出发点开始，检查一站以内（出发点的相邻点，）可以到达的地方，是否包含终点；
- step2 把一站到达的点的相邻点加入验证（即两站可达点，二级关系），是否包含终点；
- 重复step2 直到发现终点，或者相邻站点为空。
可用于解决以下问题：
- 编写国际跳棋 AI，计算最少走多少步就可获胜；
- 编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将 READED 改为 READER 需要编辑一个地方；
- 根据你的人际关系网络找到关系最近的医生。
6.1 先了解下图
（话说本科毕业论文就是用广义多项式可以描述一个图）
图，节点和边(线)组成，分有向图、无向图。
6.2 广度优先搜索
广度优先搜索是一种用于图的查找算法，可帮助回答两类问题：
第一类问题：从节点 A 出发，有前往节点 B 的路径吗？
第二类问题：从节点 A 出发，前往节点 B 的哪条路径最短？
示例问题：从社交网络朋友圈中发现一个芒果销售商？
- 可以在自己的好友中找；（一度关系）——>否——>2
- 好友中没有，就在好友的好友中找 ——>否——>2 重复，直到朋友网络为空。
这个过程中，在数据上实现时，先是将一度关系列入待检查数据，如果没有，则将二度关系依次列入待检查数据，并在一度关系检查完后再开始检查二度关系，这种数据结构称为队列。
6.3 队列
队列类似于栈，你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。
队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。
6.4 广度优先搜索实现
首先要用数据表现出这种‘相邻’，或者说好友关系。——>正好可以用 散列表。
上面的 ‘朋友圈’图，在python中即可以用字典来表示：
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_queue = deque() ←------------创建一个队列
search_queue += graph["you"] ←------将你的邻居都加入到这个搜索队列中
然后循环检查：
while search_queue: ←------只要队列不为空
person = search_queue.popleft() ←------就取出其中的第一个人
if person_is_seller(person): ←------检查这个人是否是芒果销售商
print person + " is a mango seller!" ←------是芒果销售商
return True
else:
search_queue += graph[person] ←------不是芒果销售商。将这个人的朋友都加入搜索队列
return False ←------如果到达了这里，就说明队列中没人是芒果销售商
6.5 避免重复检查
二度关系中可能有人同时和一度关系中的两个以及相关，这时可能出现两次入队的情况，容易造成循环检查。
解决办法是建立一个已检查清单，若已检查，则不再重复检查。
6.6 运行时间
广度优先搜索是沿图的边逐一进行的，故运行时间首先是 边数；
在运行过程中还创建了一个待检查清单，该清单最大数量即是所有节点，所以，广度优先搜索的运行时间为 O(人数 + 边数)，这通常写作 O(V + E).
