資料結構（十）：最小生成樹

最小生成樹是帶權無向連通圖中權值最小的生成樹，根據

圖

中生成樹定義可知，

個頂點的連通圖中，生成樹中邊的個數為

，向生成樹中添加任意一條邊，則會形成環。生成樹存在多種，其中權值之和最小的生成樹即為最小生成樹。

最小生成樹保證最小權值是固定的，但是最小生成樹可能有多個。

若

為最小生成樹

的一個真子集，即

的頂點集合和邊集合都是

的頂點和邊集合的子集，構造最小生成樹過程為向

中添加頂點和邊，添加的原則有兩種：

1. 選擇

   

   的邊集合外，權值最小的邊，加入到

   

   中

添加邊的過程需要避免形成環。

1. 

   的頂點集合外，距離

   

   最近的頂點，加入到

   

距離

最近的點，即和

中的頂點形成最小權值邊的非

中的某個頂點。

kruskal 算法

kruskal

算法即為上述第一種原則，通過選擇圖中的最小權值邊來構造最小生成樹，過程中需要注意避免形成環。

算法過程

1. 對邊集合進行排序
2. 選擇最小權值邊，若不構成環，則添加到集合

   

3. 重複執行步驟 2，直到添加

   

   條邊

示範示例

graph

step 1：

最小權值邊為頂點 7、8 形成的邊

step 2：

最小權值邊為頂點 3、9 形成的邊

step 3：

最小權值邊為頂點 6、7 形成的邊

step 4：

最小權值邊為頂點 3、6 形成的邊

step 5：

最小權值邊為頂點 1、2 形成的邊

step 6：

最小權值邊為頂點 3、4 形成的邊

step 7：

最小權值邊為頂點 1、8 形成的邊

step 8：

最小權值邊為頂點 4、5 形成的邊

最小生成樹的權值之和為 37

算法示例

這裡使用鄰接表作為圖的存儲結構

1. kruskal

def kruskal(graph):
    edges, vertices = getEdgesFromAdjacencyList(graph), [i for i in range(graph.number)]
    sort(edges, 0, len(edges) - 1)
    weightSum, edgeNumber = 0, 0
    while edgeNumber < graph.number - 1:
        edge = edges.pop()
        beginOrigin, endOrigin = origin(vertices, edge.begin - 1), origin(vertices, edge.end - 1)
        if (beginOrigin != endOrigin): # whether the two vertices belong to same graph
            vertices[beginOrigin] = endOrigin  # identify the two vertices in the same sub graph
            weightSum, edgeNumber = weightSum + edge.weight, edgeNumber + 1  # calculate the total weight
           

這裡使用

getEdgesFromAdjacencyList

函數完成鄰接表到邊集合的轉換，使用快排

sort

完成對邊集合的排序，使用

origin

函數傳回每個子圖的根。

kruskal

算法設定最初每個頂點都是一個子圖，每個子圖都有一個根，或者稱之為出發點，每個加入的頂點都保留一個指向上一個頂點的引用，并最終追溯到該子圖的根頂點，是以可以通過判斷兩個頂點指向的根頂點是否相同，來判斷兩頂點是否屬于同一個子圖。

1. 鄰接表轉邊集合

def getEdgesFromAdjacencyList(graph):
    edges = []
    for i in range(graph.number):
        node = graph.list[i]
        while node:
            edge, node = Edge(i + 1, node.index, node.weight), node.next
            edges.append(edge)
    return edges
           

因為使用鄰接表向邊進行轉化，且後續隻對邊集合進行處理，是以在測試時候，無向圖中的每條邊，隻需要記錄一次即可，不需要對于邊的兩個頂點，分别記錄一次。

1. 判斷兩個頂點是否屬于同一個子圖，避免添加邊後形成環

def origin(vertices, index):
    while vertices[index] != index:
        index = vertices[index]
    return index
           

該函數傳回頂點

index

所屬子圖的根頂點，其中

vertices[index]

位置上存儲的是頂點

index

的上一個頂點，每個子圖中，根頂點的上一個頂點為自身。

性能分析

kruskal

算法中使用

getEdgesFromAdjacencyList

函數完成鄰接表向邊集合的轉換，函數内部存在兩層循環，通路鄰接表中每個頂點的相鄰頂點，複雜度為

。使用快排對邊集合進行排序，時間複雜度為

，因為

，是以快排時間複雜度可以表述為

。

kruskal

算法中

while

循環取最小權值邊，并對邊的兩個頂點執行

origin

函數判斷是否屬于同一個子圖，時間複雜度為

。是以

kruskal

算法的時間複雜度為

prim 算法

kruskal

算法的過程為不斷對子圖進行合并，直到形成最終的最小生成樹。

prim

算法的過程則是隻存在一個子圖，不斷選擇頂點加入到該子圖中，即通過對子圖進行擴張，直到形成最終的最小生成樹。

擴張過程中選擇的頂點，是距離子圖最近的頂點，即與子圖中頂點形成的邊是權值最小的邊。

1. 按照距離子圖的遠近，對頂點集合進行排序
2. 選擇最近的頂點加入到子圖中，并更新相鄰頂點對子圖的距離
3. 重複執行步驟 2，直到頂點集合為空

這裡不妨以頂點 5 作為子圖中的第一個頂點

距離子圖的最近頂點為 4

距離子圖的最近頂點為 3

距離子圖的最近頂點為 9

距離子圖的最近頂點為 6

距離子圖的最近頂點為 7

距離子圖的最近頂點為 8

距離子圖的最近頂點為 2

距離子圖的最近頂點為 1

1. prim

def prim(graph, index):
    vertices, verticesIndex = [{'index': i, 'weight': None} for i in range(graph.number)], [i for i in range(graph.number)]
    weightSum, vertices[index - 1]['weight'] = 0, 0
    heapSort(vertices, verticesIndex)
    while len(vertices) > 0:
        swapVertices(vertices, verticesIndex, 0, -1)
        vertex = vertices.pop()
        transformToHeap(vertices, verticesIndex, 0, len(vertices))
        weightSum = weightSum + vertex['weight']
        updateVertices(graph, vertices, verticesIndex, vertex['index'])
           

vertices

清單存儲每個頂點元素，每個元素包括兩個屬性，

index

為頂點下标，

weight

為頂點距離子圖的大小。算法中使用

verticesIndex

清單存儲每個頂點元素在

vertices

清單中的下标位置。使用

heapSort

堆排序對每個頂點到子圖的距離進行排序，即對

vertices

清單進行排序，使用堆排序内的

transformToHeap

函數調整

vertices

清單為小頂堆。當添加新頂點到子圖後，使用

updateVertices

函數完成對相鄰頂點的距離更新。

因為對

vertices

清單排序後，每個頂點元素在

vertices

清單的下标值不能表示該頂點的編号，而後續添加新頂點後，在更新相鄰頂點距離的操作中，為了避免查找相鄰頂點而周遊整個清單，需要根據頂點編号進行直接通路相鄰頂點，是以借助

verticesIndex

vertices

清單中的位置。例如要更新頂點

的距離，則

verticesIndex[v]

值為頂點

在

vertices

清單中的位置，

頂點元素即為

vertices[verticesIndex[v]]

1. 交換堆頂元素

def swapVertices(vertices, verticesIndex, origin, target):
    vertices[origin], vertices[target] = vertices[target], vertices[origin]
    verticesIndex[vertices[origin]['index']], verticesIndex[vertices[target]['index']] = origin, target
           

當

vertices

清單調整為小頂堆之後，将清單首、尾元素交換，則清單尾元素即為距離子圖最近的頂點元素。

1. 添加頂點到子圖中後，更新相鄰頂點到子圖的距離

def updateVertices(graph, vertices, verticesIndex, index):
    node = graph.list[index]
    while node:
        if verticesIndex[node.index - 1] == -1:
            node = node.next
            continue
        vertex = vertices[verticesIndex[node.index - 1]]
        if not vertex['weight'] or (vertex['weight'] and vertex['weight'] > node.weight):
            vertex['weight'] = node.weight
            pos = verticesIndex[vertex['index']]
            while pos > 0 and (not vertices[(pos - 1) // 2]['weight'] or vertices[pos]['weight'] < vertices[(pos - 1) // 2]['weight']):
                swapVertices(vertices, verticesIndex, pos, (pos - 1) // 2)
                pos = (pos - 1) // 2
        node = node.next
           

對每一個相鄰頂點，如果不在子圖中，則判斷是否更新到子圖的距離。

prim

算法中構造頂點清單的時間複雜度為

。使用堆排序對頂點清單進行排序，時間複雜度為

prim

while

循環取最近頂點元素，并調整元素取出後清單的堆結構，是以總體的調整複雜度為

；同時循環結構内執行

updateVertices

函數，更新每個取出頂點的相鄰頂點距離值，是以總體的更新頂點數為

，因為每個頂點更新距離後，需要調整堆結構為小頂堆，是以總體的複雜度為

prim

代碼及測試

github

連結： 最小生成樹