本章內(nèi)容

1. 通用深度優(yōu)先DFS算法
2. 單源最短路徑問題
3. 最小生成樹

一、通用深度優(yōu)先DFS算法

一般的深度優(yōu)先搜索目標(biāo)是在圖上進(jìn)行盡量深的搜索，連接盡量多的頂點(diǎn)，必要時(shí)可以進(jìn)行分支（創(chuàng)建了樹） 有時(shí)候深度優(yōu)先搜索會(huì)創(chuàng)建多棵樹，稱為“深度優(yōu)先森林”。深度優(yōu)先搜索同樣要用到頂點(diǎn)的“前驅(qū)” 屬性，來構(gòu)建樹或森林，另外要設(shè)置“發(fā)現(xiàn)時(shí)間”和“結(jié)束時(shí)間”屬性。

• 前者是在第幾步訪問到這個(gè)頂點(diǎn)（設(shè)置灰色）
• 后者是在第幾步完成了此頂點(diǎn)探索（設(shè)置黑色）

與BFS的區(qū)別在于，在添加兄弟節(jié)點(diǎn)之前，先添加層次。

代碼實(shí)現(xiàn)：

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

    def dfs(self):
        '''
        可能會(huì)生成多個(gè)深度優(yōu)先搜索森林
        '''
        #顏色初始化
        for aVertex in self:#父類已經(jīng)實(shí)現(xiàn)了iter()方法
            aVertex.setColor('White')
            aVertex.setPred(-1)
        #如果還有未包括的頂點(diǎn)，則建森林
        for aVertex in self:
            if aVertex.getColor() == 'White':
                self.dfsvisit(aVertex)

    def dfsvisit(self, rootVertex):
        '''
        不同于BTS中的隊(duì)列，這里的遞歸隱式使用了棧
        '''
        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)

即一個(gè)頂點(diǎn)的“發(fā)現(xiàn)時(shí)間”總小于所有子頂點(diǎn)的“發(fā)現(xiàn)時(shí)間” 而“結(jié)束時(shí)間”則大于所有子頂點(diǎn)“結(jié)束時(shí)間” 比子頂點(diǎn)更早被發(fā)現(xiàn)，更晚被結(jié)束探索，類比括號(hào)和子括號(hào)的關(guān)系。

DFS算法分析：

dfs函數(shù)中有兩個(gè)循環(huán)，每個(gè)都是|V|次，所以 是O(|V|)。而dfsvisit函數(shù)中的循環(huán)則是對(duì)當(dāng)前頂點(diǎn)所連接的頂點(diǎn)進(jìn)行，而且僅有在頂點(diǎn)為白色的情況下才進(jìn)行遞歸調(diào)用，所以對(duì)每條邊來說只會(huì)運(yùn)行一 步，所以是O(|E|) 加起來就是和BFS一樣的O(|V|+|E|)。

DFS算法的應(yīng)用：

1、拓?fù)渑判?/h5>

拓?fù)渑判蛱幚硪粋€(gè)DAG，輸出頂點(diǎn)的線性序列，使得兩個(gè)頂點(diǎn)v,w，如果G中有(v,w)邊，在線性序列中v就出現(xiàn)在w之前。

在如上所示的DFS之中，進(jìn)行拓?fù)渑判蚍浅７奖惆凑誺ertex中finish從大到小的順序，即可快速完成拓?fù)渑判颉?/p>

2、強(qiáng)連通分支

定義：

圖G的一個(gè)子集C，C中的任意兩個(gè)頂點(diǎn)v,w之間都有路徑來回，即 (v,w)(w,v)都是C的路徑， 而且C是具有這樣性質(zhì)的最大子集。

在圖中發(fā)現(xiàn)高度聚集節(jié)點(diǎn)群的算法，即尋找“強(qiáng)連通分支Strongly Connected Components”算法。一旦找到強(qiáng)連通分支，可以據(jù)此對(duì)圖的頂點(diǎn)進(jìn)行分類，并對(duì)圖進(jìn)行化簡(jiǎn)。

示例：

先熟悉一個(gè)概念：Transposition轉(zhuǎn)置

一個(gè)有向圖G的轉(zhuǎn)置G^T，定義為將圖G的所有邊的頂點(diǎn)交換次序，如將(v,w)轉(zhuǎn)換為(w,v) 可以觀察到圖和轉(zhuǎn)置圖在強(qiáng)連通分支的數(shù)量和劃分上，是相同的。

Kosaraju算法:

對(duì)G進(jìn)行DFS，獲得每個(gè)vertex的finish
G進(jìn)行轉(zhuǎn)置得到GT
對(duì)GT使用DFS（注意在每個(gè)頂點(diǎn)的搜索循環(huán)中，要以頂點(diǎn)的結(jié)束時(shí)間倒序順序進(jìn)行搜索）得到深度優(yōu)先森林，那么其中的每一棵樹都是一個(gè)強(qiáng)連通分支

示例：

第一趟：

第二趟：

結(jié)果：

二、單源最短路徑問題

目標(biāo)：獲得從一個(gè)節(jié)點(diǎn)出發(fā)到達(dá)圖中任意頂點(diǎn)的最短距離。

解決帶權(quán)圖的最短路徑問題，與使用BFS解決詞梯問題非常相似，只不過邊中帶了權(quán)重。這里使用Dijkstra算法，迭代得出一個(gè)頂點(diǎn)到所有頂點(diǎn)的最短路徑。實(shí)現(xiàn)上在Vertex類中添加dist來存儲(chǔ)起點(diǎn)到本結(jié)點(diǎn)的最短權(quán)重之和，頂點(diǎn)的訪問次序由優(yōu)先隊(duì)列控制。隊(duì)列中作為優(yōu)先級(jí)的是dist，具有最小dist的結(jié)點(diǎn)出隊(duì)，計(jì)算其它結(jié)點(diǎn)的權(quán)重和，引起堆的重排，隨后根據(jù)更新dist優(yōu)先級(jí)再依次出隊(duì)。注意Dijkstra只能處理權(quán)值為正的帶權(quán)圖。

代碼實(shí)現(xiàn)：

def dijkstra(graph, start):
    #對(duì)所有頂點(diǎn)建堆形成優(yōu)先隊(duì)列
    pq = PriorityQueue()
    start.setDistance(0)
    pq.buildHeap([(v.getDistance(), v) for v in graph])
    while not pq.empty():
        #優(yōu)先隊(duì)列出隊(duì)
        currentVert = pq.delmin()
        #修改鄰接頂點(diǎn)dist，并逐個(gè)重排隊(duì)列
        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算法需要具備整個(gè)圖的數(shù)據(jù)，涉及巨大數(shù)據(jù)量的問題，同時(shí)動(dòng)態(tài)變化的數(shù)據(jù)特性也使得保存全圖缺乏現(xiàn)實(shí)性。

Dijkstra算法分析：

首先，將所有頂點(diǎn)加入優(yōu)先隊(duì)列并建堆，時(shí)間復(fù)雜度為O(|V|) 。其次，每個(gè)頂點(diǎn)僅出隊(duì)1次，每次delMin 花費(fèi)O(log|V|)，一共就是O(|V|log|V|) 。另外，每個(gè)邊關(guān)聯(lián)到的頂點(diǎn)會(huì)做一次 decreaseKey操作（O(log|V|))，一共是O(|E|log|V|) 。上面三個(gè)加在一起，數(shù)量級(jí)就是O((|V|+|E|)log|V|)。

三、最小生成樹

生成樹：

擁有圖中所有的頂點(diǎn)和最少數(shù)量的邊， 以保持連通的子圖。

圖G(V,E)的最小生成樹，指包含所有節(jié)點(diǎn)v，以及E的無圈子集，并且邊的權(quán)重之和最小。

解決：

最小生成樹問題的Prim算法，屬于 “貪心算法” ，即每步都沿著最小權(quán)重的邊向前搜索。

思路：

if T還不是生成樹：
    則反復(fù)做：
        找到一條最小權(quán)重的可以安全添加的邊
        將邊添加到樹T

“可以安全添加”的邊:

定義為一端頂點(diǎn)在樹中，另一端不在樹中的邊，以便保持樹的無圈特性。

代碼實(shí)現(xiàn)：

def prim(G,start):
    pq = PriorityQueue()
    # 節(jié)點(diǎn)初始化
    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的距離，根據(jù)distance進(jìn)行重排
        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)