此图非彼图，今天来学习一种十分重要，在生活中也经常使用的数据结构「图」
一、图
图就是由一些点与边组成，点之间是边，边两头有点，类似于我们所画的思维导图。根据点之间连接的边是否有具体指向区分为『有向图』和『无向图』。
图可以做什么呢？它可以解决最经典的问题『寻找最短路径』。类似于地图，如想知道从别墅到公司走哪条路最短，可以通过图来建立模型，将十字路口（三叉路口等连接几条路的路口）看作是点，每条路就是边，别墅是起点，公司是终点。
上面只完成了第一步，有了图之后，该如何寻找最短路径呢？下面就需要再介绍一种图算法『广度优先搜索』
二、广度优先搜索算法
广度优先搜索算法可以通过一个例子进行描述：小明想通过走动，帮助儿子进入县一中（当地最好的学校）。于是他开始回忆自己的朋友是否有县一中的领导或者认识其领导，思考之后发现并没有，然后让朋友询问朋友的朋友是否有关系。像这样，为了在社交网络中寻找到关系，先看自己（自己肯定不是，要不然直接安排了），然后将所有朋友加入到搜索名单中，看朋友中是否有关系，如果没有，再将朋友的朋友纳入范围继续寻找 ...... 直到找到需要的人，这就是广度优先搜索算法。
因为同朋友的亲密度比同朋友的朋友之间的亲密度要高，所以先从朋友之间寻找。如果将朋友比做是第一层关系，朋友的朋友为第二层，这样一层一层下去的就是广度优先搜索。如果找到一个朋友，就寻找他的朋友中是否有这样的人，如此以深度挖掘的方式搜索下去，就是深度优先搜索。
它常用于寻找两地点或者两样物体之间的最短距离。总结为下面两种问题：
•从一点可以到另一点吗？•从一点到另一点哪条路径最短？
现实生活中的例子有：
•各种智能机器，比如跳棋最少走几步可以获胜•到目的地的最短路线
在搜索的过程中，大家可能注意到，先检查朋友，后检查朋友的朋友，是有顺序的，那么如何保持顺序呢？那就需要使用到另外一种数据结构『队列』
三、队列
队列很简单，和生活中的排队一样，比如购票，结账时，先排队的人先买到票或者结账完成。就是有顺序，先进先出（First In First Out）的一种数据结构，它只有两种行为，入队和出队。类比生活中排队，有素质的人不能出现插队吧？
队列常常与栈进行对比，栈是一种先进后出的数据结构，或描述为后进先出（
Last In First Out）深度优先搜索就常使用栈。
四、实现图
代码如何实现图呢？首先图由多个节点构成，每个节点与邻近节点相连，要表示这种关系，可以联想到『散列表』，其映射关系可以将键映射到一个值或多个值。在 Python 中则使用字典表示：
graph = {}graph["小明"] = ["小花", "小玉", ...]graph["小玉"] = ["小帆", ...]
散列表是无序的
五、实现图算法
还是沿用小明为儿子学校找关系的示例，实现代码如下：
# 该字典表示图，其中将小明与朋友，小明朋友与朋友的朋友之间的关系 graph = {......} def person_is_seller(name): # 具体判断过程省略，该函数返回 true 或 false，即是或者不是 pass def search(name): # 创建一个队列 search_queue = deque() # 为队列中不断添加朋友或者朋友的朋友，即要搜索的人 search_queue += graph[name] # 这个列表用于记录检查过的人 searched = [] # 只要队列不为空就一直搜索下去 while search_queue: # 取出队列中左面第一个人 person = search_queue.popleft() # 仅当这个人没检查过时才检查 if not person in searched: # 看这个人是否是小明需要找的关系 if person_is_seller(person): # 是的话输出是要找的关系 print(person + " is the one you are looking for!") # 结束循环 return True else: # 把这个人的朋友添加到队列中 search_queue += graph[person] # 将这个人标记为检查过 searched.append(person) return False search("小明")
