数据结构-图

一、图

图就是由一些点与边组成，点之间是边，边两头有点，类似于我们所画的思维导图。根据点之间连接的边是否有具体指向区分为『有向图』和『无向图』。

图可以做什么呢？它可以解决最经典的问题『寻找最短路径』。类似于地图，如想知道从别墅到公司走哪条路最短，可以通过图来建立模型，将十字路口（三叉路口等连接几条路的路口）看作是点，每条路就是边，别墅是起点，公司是终点。

上面只完成了第一步，有了图之后，该如何寻找最短路径呢？下面就需要再介绍一种图算法『广度优先搜索』

二、广度优先搜索算法

广度优先搜索算法可以通过一个例子进行描述：小明想通过走动，帮助儿子进入县一中（当地最好的学校）。于是他开始回忆自己的朋友是否有县一中的领导或者认识其领导，思考之后发现并没有，然后让朋友询问朋友的朋友是否有关系。像这样，为了在社交网络中寻找到关系，先看自己（自己肯定不是，要不然直接安排了），然后将所有朋友加入到搜索名单中，看朋友中是否有关系，如果没有，再将朋友的朋友纳入范围继续寻找 ...... 直到找到需要的人，这就是广度优先搜索算法。

因为同朋友的亲密度比同朋友的朋友之间的亲密度要高，所以先从朋友之间寻找。如果将朋友比做是第一层关系，朋友的朋友为第二层，这样一层一层下去的就是广度优先搜索。如果找到一个朋友，就寻找他的朋友中是否有这样的人，如此以深度挖掘的方式搜索下去，就是深度优先搜索。

它常用于寻找两地点或者两样物体之间的最短距离。总结为下面两种问题：

•从一点可以到另一点吗？•从一点到另一点哪条路径最短？

现实生活中的例子有：

•各种智能机器，比如跳棋最少走几步可以获胜•到目的地的最短路线

在搜索的过程中，大家可能注意到，先检查朋友，后检查朋友的朋友，是有顺序的，那么如何保持顺序呢？那就需要使用到另外一种数据结构『队列』

三、队列

队列很简单，和生活中的排队一样，比如购票，结账时，先排队的人先买到票或者结账完成。就是有顺序，先进先出（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("小明")