目录
1）图简介
2）图是什么
3）广度优先搜索
4）实现图
5）实现算法
6）小结
本章内容;
学习使用新的数据结构图来建立网络模型； 学习广度优先搜索； 学习有向图和无向图； 学习拓扑排序，这种排序算法指出了节点之间的依赖关系。
1）图简介
假设你住在旧金山，要从双子峰前往金门大桥。你想乘公交车前往，并希望换乘最少。可乘坐的公交车如下：
从图中我们可以发现，前往进门大桥的最短路径需要三步，这种问题被称为最短路径问题(shorterst-path problem)。
要确定如何从双子峰前往金门大桥，需要两个步骤：
使用图来建立问题模型。
使用广度优先搜索解决问题。
2）图是什么
图模拟一组连接，图由节点(node)和边(edge)组成。
3）广度优先搜索
广度优先搜索是一种用于图的查找算法。可回答两类问题：
从A节点有前往节点B的路径吗？哪条路径最短？
下面来看一个例子：假设你经营这一个芒果农场，需要寻找芒果经销商，以便将芒果卖给他。为此，你可在朋友中查找。
这种查找很简单，首先创建一个朋友名单。然后依次检查名单中的每个人，看看他是否是芒果销售商。
假设你没有朋友是芒果销售商，那么你必须在朋友的朋友中查找。
检查名单中的每个人时，你都将其朋友加入名单。
1.查找最短路径
人物关系如图所示：
在你看来，一度关系胜过二度关系，二度关系胜过三度关系，等等。因此，你应现在一度关系中搜索，确定其中没有芒果销售商后，才在二度关系中搜索。广度优先搜索就是这样做的！
2.队列
队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你讲先上车。队列只有两种操作：入队和出队。
队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out, LIFO）的数据结构。
4）实现图
使用散列表，表示节点与节点之间的关系！
有向图与无向图关系如图：
5）实现算法
概述一下算法原理：
寻找芒果销售商的Python源码为：
#从标准库导入队列元素from collections import dequedef person_is_seller(name):return name[-1] == 'm'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]# This array is how you keep track of which people you've searched before.searched = []while search_queue:#队首元素出队person = search_queue.popleft()# Only search this person if you haven't already searched them.if not person in searched:if person_is_seller(person):print person + " is a mango seller!"return Trueelse:search_queue += graph[person]# Marks this person as searchedsearched.append(person)return Falsesearch("you")
