本章內(nèi)容

1. 圖的定義與基本概念
2. 圖抽象數(shù)據(jù)類型定義
3. 實(shí)現(xiàn)ADT Graph
4. 應(yīng)用：解決詞梯問題

一、圖的定義與基本概念

圖Graph是比樹更為一般的結(jié)構(gòu)，也是由節(jié)點(diǎn)和邊構(gòu)成實(shí)際上樹是一種具有特殊性質(zhì)的圖。

頂點(diǎn)vertex（節(jié)點(diǎn)Node）：

圖的基本組成部分，頂點(diǎn)具有名稱標(biāo)識(shí)Key， 也可以攜帶數(shù)據(jù)項(xiàng)payload。

邊Edge（弧Arc）：

作為2個(gè)頂點(diǎn)之間關(guān)系的表示，邊連接兩個(gè)頂點(diǎn)； 邊可以是無向或者有向的，相應(yīng)的圖稱作“無向 圖”和“有向圖”。

權(quán)重Weight：

為了表達(dá)從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的“代價(jià)”， 可以給邊賦權(quán)。

圖的定義：

圖G可以定義為G=(V, E)，其中V是頂點(diǎn)的集合，E是邊的集合，E中的每條邊e=(v, w)，v和w都是V中的頂點(diǎn)；如果是賦權(quán)圖，則可以在e中添加權(quán)重分量

子圖：

V和E的子集

路徑Path：

圖中的路徑，是由邊依次連接起來的頂點(diǎn)序列； 無權(quán)路徑的長(zhǎng)度為邊的數(shù)量；帶權(quán)路徑的長(zhǎng)度為 所有邊權(quán)重的和。

圈Cycle：

圈是首尾頂點(diǎn)相同的路徑，如上圖中 (v5,v2,v3,v5)是一個(gè)圈。如果有向圖中不存在任何圈，則稱作“有向無圈圖directed acyclic graph: DAG” ，后面我們可以看到如果一個(gè)問題能表示成DAG， 就可以用圖算法很好地解決。

二、圖抽象數(shù)據(jù)類型

定義并實(shí)現(xiàn)ADT Graph

1、定義其操作：

• Graph()：創(chuàng)建一個(gè)空的圖；
• addVertex(vert)：將頂點(diǎn)vert加入圖中
• addEdge(fromVert, toVert)：添加有向邊
• addEdge(fromVert, toVert, weight)：添加帶權(quán)的有向邊
• getVertex(vKey)：查找名稱為vKey的頂點(diǎn)
• getVertices()：返回圖中所有頂點(diǎn)列表
• in：按照vert in graph的語句形式，返回頂點(diǎn) 是否存在圖中True/False

ADT Graph的實(shí)現(xiàn)方法主要有兩種形式，鄰接矩陣與鄰接表，兩種方法各有優(yōu)劣，需要在不同應(yīng)用中加以選擇。

鄰接矩陣：

矩陣的每行和每列都代表圖中的頂點(diǎn)，如果兩個(gè)頂點(diǎn)之間有邊相連，設(shè)定行列值，無權(quán)邊則將矩陣分量標(biāo)注為1，或者0，帶權(quán)邊則將權(quán)重保存為矩陣分量值。

如果圖中的邊數(shù)很少則效率低下，成為“稀疏sparse”矩陣 而大多數(shù)問題所對(duì)應(yīng)的圖都是稀疏的，邊遠(yuǎn)遠(yuǎn)少于|V|²這個(gè)量級(jí)。

鄰接表：

可以成為稀疏圖 的更高效實(shí)現(xiàn)方案，維護(hù)一個(gè)包含所有頂點(diǎn)的主列表（master list） 主列表中的每個(gè)頂點(diǎn)，再關(guān)聯(lián)一個(gè)與自身有邊連接的所有頂點(diǎn)的列表。

鄰接列表法的存儲(chǔ)空間緊湊高效，很容易獲得頂點(diǎn)所連接的所有頂點(diǎn)，以及連接邊的信息。

三、實(shí)現(xiàn)ADT Graph

需要實(shí)現(xiàn)Vertex與Graph兩個(gè)類

實(shí)現(xiàn)Vertex類：

class Vertex:
    '''
    節(jié)點(diǎn)類數(shù)據(jù)結(jié)構(gòu)定義，包含頂點(diǎn)信息，包含邊信息。
    采用字典描述臨界列表
    '''
    def __init__(self, key):
        '''
        connectedTo字典中的鍵值對(duì)類型為'vertex:weight'
        '''
        self.id = key
        self.connectedTo = {}
        
        # 以下為BFS染色使用
        self.distance = sys.maxsize
        self.color = 'White'
        self.pred = None
        
        # 以下為DFS遍歷使用：發(fā)現(xiàn)時(shí)間與結(jié)束時(shí)間
        self.discovery = sys.maxsize
        self.finish = sys.maxsize

    def addNeighbour(self,nbr,weight = 0):
        self.connectedTo[nbr] = weight

    def __str__(self):
        '''
        v = Vertex(2)
        print(v)
        '''
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    def getconnections(self):
        '''
        獲得建立連接的節(jié)點(diǎn)
        '''
        return self.connectedTo.keys()

    def getId(self):
        return self.id
    
    def getweight(self,nbr):
        '''
        獲得到某個(gè)鄰居的路徑權(quán)重
        '''
        return self.connectedTo[nbr]
    
    # 以下是BFS染色使用的函數(shù)
    def getColor(self):
        return self.color

    def getDistance(self):
        return self.distance

    def getPred(self):
        if self.pred:
            return self.pred
        else:
            return None

    def setDistance(self, distance):
        if distance > 0:
            self.distance = distance
    
    def setPred(self,pred):
        self.pred = pred

    def setColor(self, color):
        self.color = color

    # 以下為DFS遍歷使用
    def setDiscovery(self, value):
        self.discovery = value

    def setFinish(self, value):
        self.finish = value

圖Graph類的實(shí)現(xiàn)：

class Graph:
    '''
    由頂點(diǎn)構(gòu)成的圖的形式
    '''
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self, key):
        '''
        將頂點(diǎn)加入到圖中
        '''
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self, target):
        '''
        查找key為target的頂點(diǎn)
        '''
        if target in self.vertList:
            return self.vertList[target]
        else:
            return None

    def __contains__(self, n):
        return n in self.vertList

    def addEdge(self,head,tail,weight):
        '''
        添加帶權(quán)的有向邊
        '''
        if head not in self.vertList:
            newVertex = self.addVertex(head)
        if tail not in self.vertList:
            newVertex = self.addVertex(tail)
        self.vertList[head].addNeighbour(self.vertList[tail], weight)
    
    def getVertices(self):
        '''
        返回所有的頂點(diǎn)列表
        '''
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())

四、解決詞梯問題

詞梯問題：

從一個(gè)單詞演變到另一個(gè)單詞，其中的過 程可以經(jīng)過多個(gè)中間單詞。要求是相鄰兩個(gè)單詞之間差異只能是1個(gè)字母， 如FOOL變SAGE： FOOL >> POOL >> POLL >> POLE >> PALE >> SALE >> SAGE，我們的目標(biāo)是找到最短的單詞變換序列。

解決步驟：

1. 將可能的單詞之間的演變關(guān)系表達(dá)為圖
2. 采用“廣度優(yōu)先搜索 BFS”，來搜尋從開始單詞到結(jié)束單詞之間的所有有效路徑
3. 選擇其中最快到達(dá)目標(biāo)單詞的路徑

step1：構(gòu)建單詞關(guān)系圖

首先是將所有單詞作為頂點(diǎn)加入圖中，再設(shè)法建立頂點(diǎn)之間的邊，建立邊的最直接算法，是對(duì)每個(gè)頂點(diǎn)（單詞），與其它所有單詞進(jìn)行比較，如果相差僅1個(gè)字母，則建立一條邊 時(shí)間復(fù)雜度是O(n²)，對(duì)于所有4個(gè)字母的5110 個(gè)單詞，需要超過2600萬次比較。

改進(jìn)的算法是創(chuàng)建大量的桶，每個(gè)桶可以存放若干單詞，桶標(biāo)記是去掉1個(gè)字母，通配符“_”占空的單詞，所有單詞就位后，再在同一個(gè)桶的單詞之間建立邊即可

構(gòu)建單詞關(guān)系圖代碼：

def buildGraph(wordFile):
    '''
    建立關(guān)系圖
    '''
    d = {} # 桶字典，key為字符串類型，value為列表
    g = Graph()
    wfile = open(wordFile,'r')
    
    #按照文件中單詞構(gòu)建桶 
    for line in wfile:
        word = line[:-1] #去掉末尾最后一個(gè)元素(換行符)
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:#此桶第一次出現(xiàn)
                d[bucket] = [word]
    #同一個(gè)桶內(nèi)的不同單詞之間建立邊
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1, word2)
    return g

step2：采用廣度優(yōu)先搜索BFS

BFS思想：

給定圖G，以及開始搜索的起始頂點(diǎn)s。BFS搜索所有從s可到達(dá)頂點(diǎn)的邊，而且在達(dá)到更遠(yuǎn)的距離k+1的頂點(diǎn)之前，BFS會(huì)找到全部距離為k的頂點(diǎn) 可以想象為以s為根，構(gòu)建一棵樹的過程，從頂部向下逐步增加層次。廣度優(yōu)先搜索能保證在增加層次之前，添加了所有兄弟節(jié)點(diǎn)到樹中。

準(zhǔn)備工作：

為了跟蹤頂點(diǎn)的加入過程，并避免重復(fù)頂點(diǎn)，要為頂點(diǎn)增加3個(gè)屬性：

• 距離distance：從起始頂點(diǎn)到此頂點(diǎn)路徑長(zhǎng)度；
• 前驅(qū)頂點(diǎn)predecessor：可反向追溯到起點(diǎn)；
• 顏色color：標(biāo)識(shí)了此頂點(diǎn)是尚未發(fā)現(xiàn)（白色）、已經(jīng)發(fā)現(xiàn)（灰色）、還是已經(jīng)完成探索（黑色）

還需要用一個(gè)隊(duì)列Queue來對(duì)已發(fā)現(xiàn)的頂點(diǎn)進(jìn)行排列，決定下一個(gè)要探索的頂點(diǎn)（隊(duì)首頂點(diǎn)）

BFS工作過程：

從起始頂點(diǎn)s開始，作為剛發(fā)現(xiàn)的頂點(diǎn)，標(biāo)注為灰色，距離為0，前驅(qū)為None，加入隊(duì)列
接下來是個(gè)循環(huán)迭代過程：
    從隊(duì)首取出一個(gè)頂點(diǎn)作為當(dāng)前頂點(diǎn)；
    遍歷當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)
        如果是尚未發(fā)現(xiàn)的白色頂點(diǎn)：
            將其顏色改為灰色（已發(fā)現(xiàn)），距離增加1，前驅(qū)頂點(diǎn)為當(dāng)前頂點(diǎn)，加入到隊(duì)列中
    遍歷完成后
    將當(dāng)前頂點(diǎn)設(shè)置為黑色（已探索過），循環(huán)回到步驟1的隊(duì)首取當(dāng)前頂點(diǎn)

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

def BTS(graph,start):
    '''
    BFS工作過程
    '''
    start.setDistance(0)
    start.setPred(None)
    vertQueue = Queue()
    vertQueue.enqueue(start)
    while(vertQueue.size() > 0):
        currentVert = vertQueue.dequeue()
        for nbr in currentVert.getconnections():
            if nbr.getColor() == 'White':
                nbr.setColor('Gray')
                nbr.setDistance(currentVert.getDistance() + 1)
                nbr.setPred(currentVert)
                vertQueue.enqueue(nbr)
        currentVert.setColor('Black')

以某個(gè)單詞為起點(diǎn)，遍歷了所有頂點(diǎn) ，并為每個(gè)頂點(diǎn)著色、賦距離和前驅(qū)之后，即可以通過一個(gè)回溯函數(shù)來確定起點(diǎn)到任何單詞頂點(diǎn)的最短詞梯。

回溯：

def traverse(y):
    '''
    回溯找到廣度優(yōu)先所指的路徑
    y為終點(diǎn)
    x.getPred()為None表示到達(dá)起點(diǎn)
    '''
    x = y
    while(x.getPred()):
        print(x.getId())
        x = x.getPred()
    print(x.getId())

BFS算法分析：

while循環(huán)對(duì)每個(gè)頂點(diǎn)訪問一次，所以是O(|V|)，而嵌套在while中的for，由于每條邊只有在其起始頂點(diǎn)u出隊(duì)的時(shí)候才會(huì)被檢查一次。而每個(gè)頂點(diǎn)最多出隊(duì)1次，所以邊最多被檢查1次 ，一共是O(|E|) 綜合起來BFS的時(shí)間復(fù)雜度為O(|V|+|E|)。