Python描述資料結構之最小生成樹篇

前言

??本篇章主要介紹圖的最小生成樹，包括Prim演算法和Kruskal演算法，并用Python代碼實作，

1. 創建圖

??在開始之前，我們先創建一個圖，使用鄰接矩陣表示圖：

class Graph(object):
    """
    以鄰接矩陣為存盤結構創建無向網
    """
    def __init__(self, kind):
        # 圖的型別: 無向圖, 有向圖, 無向網, 有向網
        # kind: Undigraph, Digraph, Undinetwork, Dinetwork,
        self.kind = kind
        # 頂點表
        self.vertexs = []
        # 邊表, 即鄰接矩陣, 是個二維的
        self.arcs = []
        # 當前頂點數
        self.vexnum = 0
        # 當前邊(弧)數
        self.arcnum = 0

    def CreateGraph(self, vertex_list, edge_list):
        """
        創建圖
        :param vertex_list: 頂點串列
        :param edge_list: 邊串列
        :return:
        """
        self.vexnum = len(vertex_list)
        self.arcnum = len(edge_list)
        for vertex in vertex_list:
            vertex = Vertex(vertex)
            # 頂點串列
            self.vertexs.append(vertex)
            # 鄰接矩陣, 初始化為無窮
            self.arcs.append([float('inf')] * self.vexnum)
        for edge in edge_list:
            ivertex = self.LocateVertex(edge[0])
            jvertex = self.LocateVertex(edge[1])
            weight = edge[2]
            self.InsertArc(ivertex, jvertex, weight)

    def LocateVertex(self, vertex):
        """
        定位頂點在鄰接表中的位置
        :param vertex:
        :return:
        """
        index = 0
        while index < self.vexnum:
            if self.vertexs[index].data == vertex:
                return index
            else:
                index += 1

    def InsertArc(self, ivertex, jvertex, weight):
        """
        創建鄰接矩陣
        :param ivertex:
        :param jvertex:
        :param weight:
        :return:
        """
        if self.kind == 'Undinetwork':
            self.arcs[ivertex][jvertex] = weight
            self.arcs[jvertex][ivertex] = weight

??有關鄰接矩陣中頂點結點Vertex()的定義可以參考這篇博客，這里就不在貼出相應的代碼了，

2. 問題來源

??假設要在 n n n個城市之間建立通信聯絡網，則連通 n n n個城市只需要 n ? 1 n-1 n?1條線路，在每兩個城市之間都可以建立一條線路，相應地都要付出一定的經濟代價， n n n個城市之間最多可以建立 n ( n ? 1 ) 2 \frac {n(n-1)} {2} 2n(n?1)?條線路，這時，自然會考慮這樣一個問題，如何在最節省經費的前提下建立這個連通網，即如何在這些可能的線路中選擇 n ? 1 n-1 n?1條，以使花費的經費最少，
??我們可以用連通網來表示 n n n個城市以及 n n n個城市間可能建立的通信線路，其中頂點可以表示城市，邊可以表示兩個城市之間的通信線路，邊的權值就是修建這條線路所需的經費，對于 n n n個頂點的連通網可以建立許多不同的生成樹，每一棵樹都可以是一個連通網，現在要從中選擇出一棵使用經費最少的生成樹，這個問題就是構造連通網的最小代價生成樹 ( M i n i m u m (Minimum (Minimum C o s t Cost Cost S p a n n i n g Spanning Spanning T r e e ) Tree) Tree)的問題，簡稱最小生成樹 ( M S T ) (MST) (MST)問題，
??MST的性質：假設 N = ( V , { E } ) N=(V,\{E\}) N=(V,{E})是一個連通網， U U U是頂點集 V V V的一個非空子集，若 ( u , v ) (u,v) (u,v)是一條具有最小權值的邊，其中 u ∈ U , v ∈ V ? U u\in U,v\in V-U u∈U,v∈V?U，則必存在一棵包含邊 ( u , v ) (u,v) (u,v)的最小生成樹，
?? P r i m Prim Prim演算法和 K r u s k a l Kruskal Kruskal演算法是兩個利用MST性質構造最小生成樹的經典演算法，

3. Prim演算法

?? P r i m Prim Prim演算法，中文名叫普里姆演算法，基本思想如下：
??(1) 指定連通網 N N N中的某一頂點作為構造最小生成樹的起點，并令 U = { w } , T E = { } U=\{w\},TE=\{\} U={w},TE={}；
??(2) 在所有 u ∈ U 、 v ∈ V ? U u\in U、v\in V-U u∈U、v∈V?U的邊中，找到一條權值最小的邊 ( u , v ) ∈ E (u,v)\in E (u,v)∈E，將 u u u并入到 U U U中，并將邊 ( u , v ) (u,v) (u,v)并入到 T E TE TE中；
??(3) 重復執行第二步，直到 U = V U=V U=V，此時最小生成樹包含 n ? 1 n-1 n?1條邊，
??這里使用一個輔助陣列closedge，用來存盤從 U U U到 U ? V U-V U?V中權值最小的邊及頂點 U U U的下標，除此之外還需要一個串列arc來存盤最小生成樹的邊，下面結合著 P r i m Prim Prim演算法來分析一下上面的那個無向網：

??(1) P r i m Prim Prim演算法一直在更新兩個集合，即已訪問頂點集合 U U U和未訪問頂點集合 U ? V U-V U?V，然后從這兩個集合組成的邊中選擇權值最小的邊，這里以頂點 A A A為起始點，先將它加入 U U U中，即其對應的closedge置為 [ ( 0 , 0 ) ] [(0,0)] [(0,0)]，此時 U U U中只有頂點 A A A，與 A A A相連的邊有 A B AB AB、 A C AC AC和 A D AD AD，初始closedge為 [ ( 0 , 0 ) , ( 0 , 6 ) , ( 0 , 1 ) , ( 0 , 5 ) , ( 0 , ∞ ) , ( 0 , ∞ ) ] [(0,0),(0,6),(0,1),(0,5),(0,\infty),(0,\infty)] [(0,0),(0,6),(0,1),(0,5),(0,∞),(0,∞)]，其中權值最小的邊的另一個頂點索引為2，即頂點 C C C，然后根據這個索引2確定了該邊對應兩個頂點的索引 ( 0 , 2 ) (0,2) (0,2)，即邊 A C AC AC，圖中的紅色線表示，將該邊加入到串列arc中，同時將 C C C加入 U U U中，即將其對應的closedge由 ( 0 , 1 ) (0,1) (0,1)置為 ( 0 , 0 ) (0,0) (0,0)，此時closedge為 [ ( 0 , 0 ) , ( 0 , 6 ) , ( 0 , 0 ) , ( 0 , 5 ) , ( 0 , ∞ ) , ( 0 , ∞ ) ] [(0,0),(0,6),(0,0),(0,5),(0,\infty),(0,\infty)] [(0,0),(0,6),(0,0),(0,5),(0,∞),(0,∞)]；
??(2) 此時 U U U中有頂點 A A A和 C C C，然后去找兩頂點集合對應權值最小的邊，與 C C C相連的邊有 C A CA CA、 C B CB CB、 C D CD CD、 C E CE CE和 C F CF CF，更新closedge為 [ ( 0 , 0 ) , ( 2 , 5 ) , ( 0 , 0 ) , ( 0 , 5 ) , ( 2 , 6 ) , ( 2 , 4 ) ] [(0,0),(2,5),(0,0),(0,5),(2,6),(2,4)] [(0,0),(2,5),(0,0),(0,5),(2,6),(2,4)]，更新的原則是如果新邊的權重比closedge中的小，更新，否則不更新，其中權值最小的邊的另一個頂點索引為5，即頂點 F F F，然后根據這個索引5確定了該邊對應兩個頂點的索引 ( 2 , 5 ) (2,5) (2,5)，即邊 C F CF CF，圖中的橙色線表示，將該邊加入到串列arc中，同時將 F F F加入 U U U中，即將其對應的closedge由 ( 2 , 4 ) (2,4) (2,4)置為 ( 2 , 0 ) (2,0) (2,0)，此時closedge為 [ ( 0 , 0 ) , ( 2 , 5 ) , ( 0 , 0 ) , ( 0 , 5 ) , ( 2 , 6 ) , ( 2 , 0 ) ] [(0,0),(2,5),(0,0),(0,5),(2,6),(2,0)] [(0,0),(2,5),(0,0),(0,5),(2,6),(2,0)]；
??(3) 此時 U U U中有頂點 A A A、 C C C和 F F F，然后去找兩頂點集合對應權值最小的邊，與 F F F相連的邊有 F C FC FC、 F D FD FD和 F E FE FE，更新closedge為 [ ( 0 , 0 ) , ( 2 , 5 ) , ( 0 , 0 ) , ( 5 , 2 ) , ( 2 , 6 ) , ( 2 , 0 ) ] [(0,0),(2,5),(0,0),(5,2),(2,6),(2,0)] [(0,0),(2,5),(0,0),(5,2),(2,6),(2,0)]，其中權值最小的邊的另一個頂點索引為3，即頂點 D D D，然后根據這個索引3確定了該邊對應兩個頂點的索引 ( 5 , 2 ) (5,2) (5,2)，即邊 F D FD FD，圖中的黃色線表示，將該邊加入到串列arc中，同時將 D D D加入 U U U中，即將其對應的closedge由 ( 5 , 2 ) (5,2) (5,2)置為 ( 5 , 0 ) (5,0) (5,0)，此時closedge為 [ ( 0 , 0 ) , ( 2 , 5 ) , ( 0 , 0 ) , ( 5 , 0 ) , ( 2 , 6 ) , ( 2 , 0 ) ] [(0,0),(2,5),(0,0),(5,0),(2,6),(2,0)] [(0,0),(2,5),(0,0),(5,0),(2,6),(2,0)]；
??(4) 此時 U U U中有頂點 A A A、 C C C、 F F F和 D D D，然后去找兩頂點集合對應權值最小的邊，與 D D D相連的邊有 D A DA DA、 D C DC DC和 D F DF DF，更新closedge為 [ ( 0 , 0 ) , ( 2 , 5 ) , ( 0 , 0 ) , ( 5 , 0 ) , ( 2 , 6 ) , ( 2 , 0 ) ] [(0,0),(2,5),(0,0),(5,0),(2,6),(2,0)] [(0,0),(2,5),(0,0),(5,0),(2,6),(2,0)]，其中權值最小的邊的另一個頂點索引為1，即頂點 B B B，然后根據這個索引1確定了該邊對應兩個頂點的索引 ( 2 , 1 ) (2,1) (2,1)，即邊 C B CB CB，圖中的綠色線表示，將該邊加入到串列arc中，同時將 B B B加入 U U U中，，即將其對應的closedge由 ( 2 , 5 ) (2,5) (2,5)置為 ( 2 , 0 ) (2,0) (2,0)，此時closedge為 [ ( 0 , 0 ) , ( 2 , 0 ) , ( 0 , 0 ) , ( 5 , 0 ) , ( 2 , 6 ) , ( 2 , 0 ) ] [(0,0),(2,0),(0,0),(5,0),(2,6),(2,0)] [(0,0),(2,0),(0,0),(5,0),(2,6),(2,0)]；
??(5) 此時 U U U中有頂點 A A A、 C C C、 F F F、 D D D和 B B B，然后去找兩頂點集合對應權值最小的邊，與 B B B相連的邊有 B A BA BA、 B C BC BC和 B E BE BE，更新closedge為 [ ( 0 , 0 ) , ( 2 , 0 ) , ( 0 , 0 ) , ( 5 , 0 ) , ( 1 , 3 ) , ( 2 , 0 ) ] [(0,0),(2,0),(0,0),(5,0),(1,3),(2,0)] [(0,0),(2,0),(0,0),(5,0),(1,3),(2,0)]，其中權值最小的邊的另一個頂點索引為4，即頂點 E E E，然后根據這個索引4確定了該邊對應兩個頂點的索引 ( 1 , 4 ) (1,4) (1,4)，即邊 B E BE BE，圖中的藍色線表示，將該邊加入到串列arc中，同時將 E E E加入 U U U中，，即將其對應的closedge由 ( 2 , 6 ) (2,6) (2,6)置為 ( 1 , 3 ) (1,3) (1,3)，此時closedge為 [ ( 0 , 0 ) , ( 2 , 0 ) , ( 0 , 0 ) , ( 5 , 0 ) , ( 1 , 0 ) , ( 2 , 0 ) ] [(0,0),(2,0),(0,0),(5,0),(1,0),(2,0)] [(0,0),(2,0),(0,0),(5,0),(1,0),(2,0)]；
??至此，未訪問頂點的集合已為空，頂點已全部被訪問，最小生成樹為： { ( A , C ) , ( C , F ) , ( F , D ) , ( C , B ) , ( B , E ) } \{(A,C),(C,F),(F,D),(C,B),(B,E)\} {(A,C),(C,F),(F,D),(C,B),(B,E)}，
?? P r i m Prim Prim演算法實作如下：

    def GetMin(self, closedge):
        """
        找到當前closedge中權值最小的邊
        :param closedge: 
        :return: 
        """
        index = 0
        vertex = 0
        minweight = float('inf')
        while index < self.vexnum:
            if closedge[index][1] != 0 and closedge[index][1] < minweight:
                minweight = closedge[index][1]
                vertex = index
            index += 1
        return vertex

    def Prim(self, start_vertex):
        k = self.LocateVertex(start_vertex)
        closedge = []
        arc = []
        for index in range(self.vexnum):
            # 下標權值, 初始化
            closedge.append([k, self.arcs[k][index]])
        # 將起始點加入到U中
        closedge[k][1] = 0
        index = 1
        while index < self.vexnum:
            # 找到了與下標為k相連的最小邊
            minedge = self.GetMin(closedge)
            # 將當前最小權值的邊加入到最小生成樹arc
            arc.append([self.vertexs[closedge[minedge][0]].data, self.vertexs[minedge].data, closedge[minedge][1]])
            # 將最小邊權值置為0, 即將頂點v加入U中, 表示該頂點已經在最小生成樹內
            closedge[minedge][1] = 0
            i = 0
            # 重新選擇權值最小邊
            while i < self.vexnum:
                if self.arcs[minedge][i] < closedge[i][1]:
                    # 更新 最小邊的權值及下標
                    closedge[i] = [minedge, self.arcs[minedge][i]]
                i += 1
            index += 1
        return arc

??可以看到 P r i m Prim Prim演算法的時間復雜度與圖中頂點的數目有個很大關系，所以它更適合稠密網求最小生成樹，

4. Kruskal演算法

?? K r u s k a l Kruskal Kruskal演算法，中文名叫克魯斯卡爾演算法，基本思想如下：
??(1) 將連通網 N N N中的所有邊存入集合Edges，并按權值從小到大進行排列，同時令 U = V , T E = { } U=V,TE=\{\} U=V,TE={}， T E TE TE是 N N N上最小生成樹中邊的集合，此時為空，即最小生成樹 T T T中的每一個頂點都自帶一個連通分量；
??(2) 依次訪問Edges中的邊，若當前被訪問的邊的兩個頂點屬于不同的連通分量，即不構成環，則將該邊加入到 T E TE TE中，并標記當前兩個頂點所在的連通分量為同一個連通分量；否則將該邊從Edges中洗掉；
??(3) 重復執行第二步，直到最小生成樹 T T T的所有頂點均屬于同一連通分量，此時 E d g e s Edges Edges中的邊與組成最小生成樹 T T T的邊相同，這些邊組成了集合 T E TE TE，

??這里使用一個輔助陣列flags來記錄每個頂點所屬的連通分量的序號，下面結合著 K r u s k a l Kruskal Kruskal演算法來分析一下上面的那個無向網：
??(1) K r u s k a l Kruskal Kruskal演算法在不斷遍歷串列edges中的每一條邊并更新串列edges，首先遍歷第一條邊 ( A , C ) (A,C) (A,C)，圖中的紅色線，發現這條邊的兩個頂點屬于不同的連通分量，然后就更新輔助陣列flags中對應頂點的序號，讓它們倆的序號一致；
??(2) 然后遍歷下一條邊 ( D , F ) (D,F) (D,F)，圖中的橙色線，發現這條邊的兩個頂點屬于不同的連通分量，然后就更新輔助陣列flags中對應頂點的序號，讓它們倆的序號一致；
??(3) 然后遍歷下一條邊 ( B , E ) (B,E) (B,E)，圖中的黃色線，發現這條邊的兩個頂點屬于不同的連通分量，然后就更新輔助陣列flags中對應頂點的序號，讓它們倆的序號一致；
??(4) 然后遍歷下一條邊 ( C , F ) (C,F) (C,F)，圖中的綠色線，發現這條邊的兩個頂點屬于不同的連通分量，然后就更新輔助陣列flags中對應頂點的序號，讓它們倆的序號一致；
??(5) 然后遍歷下一條邊 ( A , D ) (A,D) (A,D)，發現這條邊的兩個頂點屬于相同的連通分量，即加入這條邊后，無向網就會產生回路，洗掉串列edges中的這條邊；
??(6) 然后遍歷下一條邊 ( B , C ) (B,C) (B,C)，圖中的藍色線，發現這條邊的兩個頂點屬于不同的連通分量，然后就更新輔助陣列flags中對應頂點的序號，讓它們倆的序號一致；
??(7) 然后遍歷下一條邊 ( C , D ) (C,D) (C,D)，發現這條邊的兩個頂點屬于相同的連通分量，即加入這條邊后，無向網就會產生回路，洗掉串列edges中的這條邊；
??然后繼續遍歷，直至遍歷完串列edges，串列edges中剩余的邊就構成了最小生成樹，最小生成樹為： { ( A , C ) , ( D , F ) , ( B , E ) , ( C , F ) , ( B , C ) } \{(A,C),(D,F),(B,E),(C,F),(B,C)\} {(A,C),(D,F),(B,E),(C,F),(B,C)}，
?? K r u s k a l Kruskal Kruskal演算法實作如下：

    def AddEdges(self):
        """
        將連通網中的邊加入到串列AddEdges中
        :return:
        """
        edges = []
        i = 0
        while i < self.vexnum:
            j = 0
            while j < self.vexnum:
                if self.arcs[i][j] != float('inf'):
                    edges.append([self.vertexs[i].data, self.vertexs[j].data, self.arcs[i][j]])
                j += 1
            i += 1
        # 按權重從小到大進行排序
        return sorted(edges, key=lambda item: item[2])

    def Kruskal(self):
        edges = self.AddEdges()
        flags = []
        for index in range(self.vexnum):
            flags.append(index)
        index = 0
        while index < len(edges):
            ivertex = self.LocateVertex(edges[index][0])
            jvertex = self.LocateVertex(edges[index][1])
            if flags[ivertex] != flags[jvertex]:
                # 兩個頂點不屬于同一連通分量
                # 找到它們各自的連通分量的序號
                iflag = flags[ivertex]
                jflag = flags[jvertex]
                # 它們兩個如何合并, 找找flags有沒有與之相同的
                limit = 0
                while limit < self.vexnum:
                    if flags[limit] == jflag:
                        # 將j和i的連通序號設定相同, 表示它倆是連通的
                        flags[limit] = iflag
                    limit += 1
                # index就要放這里, 因為洗掉邊后edges長度就會減少1
                index += 1
            else:
                # 已經連通了, 即加入這條邊就構成了環
                # 洗掉這條邊
                edges.pop(index)
        return edges

??可以看到 K r u s k a l Kruskal Kruskal演算法的時間復雜度與圖中邊的數目有個很大關系，所以它更適合稀疏網求最小生成樹，

5. 代碼測驗

??測驗代碼如下：

if __name__ == '__main__':
    graph = Graph(kind='Undinetwork')
    graph.CreateGraph(vertex_list=['A', 'B', 'C', 'D', 'E', 'F'],
                      edge_list=[('A', 'B', 6), ('A', 'C', 1), ('A', 'D', 5), ('B', 'C', 5),
                                 ('B', 'E', 3), ('C', 'D', 5), ('C', 'E', 6), ('C', 'F', 4),
                                 ('D', 'F', 2), ('E', 'F', 6)])
    # 起始位置的index為0
    mst1 = graph.Prim('A')
    print('Prim最小生成樹為: ')
    for edge in mst1:
        print('{0}-->{1}: {2}'.format(edge[0], edge[1], edge[2]))
    mst2 = graph.Kruskal()
    print('Kruskal最小生成樹為: ')
    for edge in mst2:
        print('{0}-->{1}: {2}'.format(edge[0], edge[1], edge[2]))

??測驗結果如下：

??B站一位大佬制作的 P r i m Prim Prim演算法和 K r u s k a l Kruskal Kruskal演算法動態演示，