章节内容
- 学习新的数据结构图来建立网络模型
- 学习广度优先搜索
- 学习有向图和无向图
- 学习拓扑排序
图
图由多个节点和节点之间的连线组合而成。
一个节点可能与众多节点直接相连，这些节点被称为邻居。
广度优先搜索
广度优先搜索(BFS)是一种图算法，用于解决两个节点的最短路径问题；两个节点是否想通。
最短路径问题比如：
- 编写国际跳棋，计算最少走多少步可以获胜
- 编写拼写检查器，计算最少编辑几个地方可以将错误单词改正确
- 根据你的人际关系网络找到关系最近的医生
查找最短路径
在人际关系网中，一度关系胜过二度关系，二度关系胜过三度关系，以此类推。
所以我们在搜索关系最近的医生时，应优先搜索一度关系，再检查二度关系。
我们需要顺序地将人际关系添加到一个数据结构中，然后进行检查。有一个可实现这种目的的数据结构就是队列。
队列
队列的工作原理和现实中的队列完全相同。
队列只支持两种操作，入队和出队（现实中的插队不算）；并且先入队的先出队(FIFO)，而之前学习的栈是先进后出
实现图
图是由节点和节点间的连线组成的，我们可以把节点间的连线当做一种映射关系，所以我们可以用用散列表来实现图。
比如表示人机关系图的python代码：
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["thom"] = ["jonny"]
上面代码中的关系是单向的，jonny是thom的邻居，但是没有指向jonny的人，所以jonny没有邻居。这种单向的图被称为有向图。
反之，直接相连的节点互为邻居则成为无向图。
实现BFS算法
我们学习了队列的工作原理，也学习了图的数据结构实现，接下来就可以实现BFS算法：
def searchDoctor(name):
search_queue = deque()
search_queue += graph[name]
searched = [] //用这个数组记录里检查过的人，防止重复检查产生死循环
while search_queue:
person = serach_queue.popleft()
if not person in searched: //当这个人没有检查过
if person_is_doctor(person):
print person + " is a doctor"
return true
else:
search_queue += graph[person]
searched.append(person) //将这个人标记为已检查
return false
searchDoctor("you")
小结
- 广度优先搜索指出是否有从A到B的路径
- 如果有，广度优先搜索将找出最短路径
- 面临类似于寻找最短路径问题，可尝试使用图来建立模型，再使用广度优先搜索来解决问题
- 有向图中的边为箭头，箭头的方向指定了关系的方向
- 无向图中的边不带箭头，其中的关系是双向的
- 队列是先进先出的
- 栈是后进先出的
- 你需要按加入顺序检查搜索列表的人，否则找到的就不是最短路径，因此搜索列表必须是队列
- 对于检查过的人，务必不要再去检查，否则可能导致无线循环