去目的地最少中转方案怎么实现?

cover

在之前的一篇文章中，我们具体讨论了计算去目的地的最少中转方案的算法，但是限于篇幅，没有介绍实现。今天，我们就来看看这个算法如何实现。

在那篇文章中我们提到，为了更快速地获取某一顶点的邻居顶点，采用图的邻接表存储信息比较合适。那么邻接表如何用Python来表达呢？

邻接表兼具数组和链表的特点。我们可以利用哈希表将表头元素和其后续的链表联系起来。在Python中，可以直接使用其内置的字典和列表数据结构来描述这里的邻接表。

图的结构举例

比如，上图的邻接表可表达为：

graph = {}
graph['A'] = ['C']
graph['B'] = ['C', 'D']
graph['C'] = ['A', 'B', 'E']
graph['D'] = ['B', 'E']
graph['E'] = ['C', 'D']

通过调用graph[顶点名]，我们可以很快的获取该点的所有邻居顶点。

除此以外，广度优先搜索需要队列保持搜索的顺序。在Python中，已有内置了队列这样的数据结构。它的基本使用方式如下：

from collections import deque # 从包中导入队列
q = deque()                   # 初始化一个空队列
q.append(<object>)            # 将某一对象（这个对象是<object>）加入队尾
<object> = q.popleft()        # 从队首弹出元素,将此元素赋值给<object>
""" P.S.
如果你细心地查看deque的文档的话，会发现它不完全是我们之前所描述的队列。
deque是一种双端队列，也就是说元素的增删操作在队头和队尾都可以。
在这里，我们限制了deque的操作来模拟队列的功能。

确定数据的存储方式后，就可以进入下一步，即如何操作这些数据，达到预期的效果。

在实现最短中转之前，我们先来看看广度优先搜索如何实现。

from collections import deque

graph = {}
graph['A'] = ['C']
graph['B'] = ['C', 'D']
graph['C'] = ['A', 'B', 'E']
graph['D'] = ['B', 'E']
graph['E'] = ['C', 'D']

def bfs_traverse():
    """
    广度优先遍历图中的顶点
    :return:无
    """
    search_queue = deque()                     # 初始化队列
    searched = []                              # 存储已经访问过的元素
    vexs = list(graph.keys())                  # 获取图中的所有顶点
    for i in range(len(graph)):                # 循环遍历
        if not vexs[i] in searched:            # 如果该顶点没有访问过
            searched.append(vexs[i])           # 标记其已被访问过
            search_queue.append(vexs[i])       # 加入队列
            while search_queue:                # 当队列非空
                vex = search_queue.popleft()   # 弹出队列中的顶点
                print(vex)                     # 打印显示
                for v in graph[vex]:           # 遍历其邻居顶点
                    if v not in searched:      # 如果邻居顶点未被访问过
                        searched.append(v)     # 标记其已被访问过
                        search_queue.append(v) # 加入队列

bfs_traverse()
"""
输出结果
A
C
B
E
D
"""

仔细观察，我们发现广度优先遍历在遍历的过程中并没有存储路径方案。如果要计算从某一点到另一点的最少中转路径，则需要存储路径信息。

那么，如何来存储路径信息呢？

这里，我们可以定义一个parents哈希表，用来存储到达某一点时的上一个顶点。初始时，每一个顶点的上一个顶点都为空。当算法处理完后，这个哈希表中就隐含着路径信息。那么究竟如何利用parents信息来给出路径呢？

我们一起来分析一个例子。如果从A出发，算法处理完后，得到如下的哈希表：

\(\{'A': None, 'B': 'C', 'C': 'A', 'D': 'B', 'E': 'C'\}\)

（为什么 \(A\) 对应的值为 \(None\) ？因为 \(A\) 是起点，在路径上没有上一个顶点。）

如果我们想到达 \(D\) ，依据哈希表，可以找到 \(D\) 的上一个点为 \(B\) ；继续找到 \(B\) 的上一个顶点为 \(C\) ， \(C\) 的上一个顶点为 \(A\) 。而 \(A\) 没有上一个顶点（即 \(A\) 为起点），所以所得路径为 \(A->C->B->D\) 。

寻找这个路径的顶点的顺序和最终输出的顺序是相反的，怎么描述方便呢？如果你还记得之前介绍过的栈，你肯定会选择栈来暂存路径数据，在输出时依次弹出即可。（栈的特点是先进后出的，因而可以利用栈把一些对象序列逆序）

为了保证最终得到的方案是最少中转，还需引入中转数。在某些情况下，更新中转数和parents哈希表中的值。中转数的存储可以另外开设哈希表存储，也可以嵌入现有的graph哈希表中。这里，我们选择第二种方案实现。

这样的话，上述 \(graph\) 就变为如下的形式

graph = {}
graph['A'] = {'C': None}
graph['B'] = {'C': None, 'D': None}
graph['C'] = {'A': None, 'B': None, 'E': None}
graph['D'] = {'B': None, 'E': None}
graph['E'] = {'C': None, 'D': None}

在这种 \(graph\) 的结构下，广度优先遍历也需要做一点简单的修改。

全部的代码如下所示：

from collections import deque

graph = {}
graph['A'] = {'C': None}
graph['B'] = {'C': None, 'D': None}
graph['C'] = {'A': None, 'B': None, 'E': None}
graph['D'] = {'B': None, 'E': None}
graph['E'] = {'C': None, 'D': None}

parents = {}
parents['A'] = None
parents['B'] = None
parents['C'] = None
parents['D'] = None
parents['E'] = None


def search(src, des):
    """
    寻找从src到des之间的最短中转方案
    :param src: 起点
    :param des: 终点
    :return: 路径（列表），中转数（整型）
    """
    search_queue = deque()
    searched = []
    level = 0
    if src not in searched:
        searched.append(src)
        search_queue.append(src)
        while search_queue:
            vex = search_queue.popleft()
            level += 1
            for v in graph[vex].keys():
                if v not in searched:
                    searched.append(v)
                    search_queue.append(v)
                    if graph[vex][v] is None or graph[vex][v] < level:
                        parents[v] = vex
                        graph[vex][v] = level
        #print(parents)
        stack = []
        road = []
        stack.append(des)
        child = des
        while not parents[child] is None:
            stack.append(parents[child])
            child = parents[child]
        while stack:
            road.append(stack.pop())

        node = src
        i = 1
        while des not in graph[node].keys():
            node = road[i]
            i += 1
        cost = graph[node][des]

        return road, cost

def bfs_traverse():
    """
    广度优先遍历图中的顶点
    :return:无
    """
    search_queue = deque()
    searched = []
    vexs = list(graph.keys())
    for i in range(len(graph)):
        if not vexs[i] in searched:
            searched.append(vexs[i])
            search_queue.append(vexs[i])
            while search_queue:
                vex = search_queue.popleft()
                print(vex)
                for v in graph[vex].keys(): # 修改！！！
                    if v not in searched:
                        searched.append(v)
                        search_queue.append(v)

# bfs_traverse()

r, c = search("A", 'E')
print("最少中转次数为{},路径为{}".format(c, ','.join(r)))

"""
输出结果：
最少中转次数为2,路径为A,C,E
"""

上述输出的结果符合我们的心理预期。这样实现就能满足所有情况了吗？答案显然是否定的，因为这种实现并没有考虑两点之间没有路径的极端情况（当然如果在现实中，这种情况出现的概率非常小）。这个函数的进一步改进留给你自己思考。

好了，本篇文章的主要内容结束了。最后是本篇的重点内容回顾。

1. 图的邻接表存储方式，在Python中可以利用字典描述
2. 利用栈可以将对象序列逆序排列。