python数据结构教程 Day16

本章内容

通用深度优先DFS算法
单源最短路径问题
最小生成树

一、通用深度优先DFS算法

一般的深度优先搜索目标是在图上进行尽量深的搜索，连接尽量多的顶点，必要时可以进行分支（创建了树）有时候深度优先搜索会创建多棵树，称为“深度优先森林”。深度优先搜索同样要用到顶点的“前驱” 属性，来构建树或森林，另外要设置“发现时间”和“结束时间”属性。

前者是在第几步访问到这个顶点（设置灰色）
后者是在第几步完成了此顶点探索（设置黑色）

与BFS的区别在于，在添加兄弟节点之前，先添加层次。

代码实现：

class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0

    def dfs(self):
        '''
        可能会生成多个深度优先搜索森林
        '''
        #颜色初始化
        for aVertex in self:#父类已经实现了iter()方法
            aVertex.setColor('White')
            aVertex.setPred(-1)
        #如果还有未包括的顶点，则建森林
        for aVertex in self:
            if aVertex.getColor() == 'White':
                self.dfsvisit(aVertex)

    def dfsvisit(self, rootVertex):
        '''
        不同于BTS中的队列，这里的递归隐式使用了栈
        '''
        rootVertex.setColor('Gray')
        self.time += 1
        rootVertex.setDiscovery(self.time)
        for nextVertex in rootVertex.getconnections():
            if nextVertex.getColor == 'White':
                nextVertex.setPred(rootVertex)
                self.dfsvisit(nextVertex)
        rootVertex.setColor('Black')
        self.time += 1
        rootVertex.setFinish(self.time)

即一个顶点的“发现时间”总小于所有子顶点的“发现时间” 而“结束时间”则大于所有子顶点“结束时间” 比子顶点更早被发现，更晚被结束探索，类比括号和子括号的关系。

DFS算法分析：

dfs函数中有两个循环，每个都是|V|次，所以是O(|V|)。而dfsvisit函数中的循环则是对当前顶点所连接的顶点进行，而且仅有在顶点为白色的情况下才进行递归调用，所以对每条边来说只会运行一步，所以是O(|E|) 加起来就是和BFS一样的O(|V|+|E|)。

DFS算法的应用：

1、拓扑排序

拓扑排序处理一个DAG，输出顶点的线性序列，使得两个顶点v,w，如果G中有(v,w)边，在线性序列中v就出现在w之前。

在如上所示的DFS之中，进行拓扑排序非常方便按照vertex中finish从大到小的顺序，即可快速完成拓扑排序。

2、强连通分支

定义：

图G的一个子集C，C中的任意两个顶点v,w之间都有路径来回，即 (v,w)(w,v)都是C的路径，而且C是具有这样性质的最大子集。

在图中发现高度聚集节点群的算法，即寻找“强连通分支Strongly Connected Components”算法。一旦找到强连通分支，可以据此对图的顶点进行分类，并对图进行化简。

示例：

先熟悉一个概念：Transposition转置

一个有向图G的转置G^T，定义为将图G的所有边的顶点交换次序，如将(v,w)转换为(w,v) 可以观察到图和转置图在强连通分支的数量和划分上，是相同的。

Kosaraju算法:

对G进行DFS，获得每个vertex的finish
G进行转置得到GT
对GT使用DFS（注意在每个顶点的搜索循环中，要以顶点的结束时间倒序顺序进行搜索）得到深度优先森林，那么其中的每一棵树都是一个强连通分支

示例：

第一趟：

第二趟：

结果：

二、单源最短路径问题

目标：获得从一个节点出发到达图中任意顶点的最短距离。

解决带权图的最短路径问题，与使用BFS解决词梯问题非常相似，只不过边中带了权重。这里使用Dijkstra算法，迭代得出一个顶点到所有顶点的最短路径。实现上在Vertex类中添加dist来存储起点到本结点的最短权重之和，顶点的访问次序由优先队列控制。队列中作为优先级的是dist，具有最小dist的结点出队，计算其它结点的权重和，引起堆的重排，随后根据更新dist优先级再依次出队。注意Dijkstra只能处理权值为正的带权图。

代码实现：

def dijkstra(graph, start):
    #对所有顶点建堆形成优先队列
    pq = PriorityQueue()
    start.setDistance(0)
    pq.buildHeap([(v.getDistance(), v) for v in graph])
    while not pq.empty():
        #优先队列出队
        currentVert = pq.delmin()
        #修改邻接顶点dist，并逐个重排队列
        for nextVertex in currentVert.getconnections():
            newDist = currentVert.getDistance() + currentVert.getweight(nextVertex)
            if newDist < nextVertex.getDistance():
                nextVertex.setDistance(newDist)
                nextVertex.setPred(currentVert)
                pq.decreaseKey(nextVertex, newDist)

Dijkstra算法需要具备整个图的数据，涉及巨大数据量的问题，同时动态变化的数据特性也使得保存全图缺乏现实性。

Dijkstra算法分析：

首先，将所有顶点加入优先队列并建堆，时间复杂度为O(|V|) 。其次，每个顶点仅出队1次，每次delMin 花费O(log|V|)，一共就是O(|V|log|V|) 。另外，每个边关联到的顶点会做一次 decreaseKey操作（O(log|V|))，一共是O(|E|log|V|) 。上面三个加在一起，数量级就是O((|V|+|E|)log|V|)。

三、最小生成树

生成树：

拥有图中所有的顶点和最少数量的边，以保持连通的子图。

图G(V,E)的最小生成树，指包含所有节点v，以及E的无圈子集，并且边的权重之和最小。

解决：

最小生成树问题的Prim算法，属于 “贪心算法” ，即每步都沿着最小权重的边向前搜索。

思路：

if T还不是生成树：
    则反复做：
        找到一条最小权重的可以安全添加的边
        将边添加到树T

“可以安全添加”的边:

定义为一端顶点在树中，另一端不在树中的边，以便保持树的无圈特性。

代码实现：

def prim(G,start):
    pq = PriorityQueue()
    # 节点初始化
    for v in G:
        v.setDistance(sys.maxsize)
        v.setPred(None)
    start.setDistance(0)
    pq.buildHeap([(v.getDistance(), v) for v in G])
    while not pq.empty():
        currentVert = pq.delmin()
        # distsance仅代表从current到next的距离，根据distance进行重排
        for nextVert in currentVert.getconnections():
            newCost = currentVert.getweight(nextVert)
            if nextVert in pq and newCost < nextVert.getDistance():
                nextVert.setPred(currentVert)
                nextVert.setDistance(newCost)
                pq.decreasekey(nextVert, newCost)