最小生成樹-有解無憂

如下圖是個帶權值的網結構圖，要用最小的成本將所有元素連接起來，即n個頂點，用n-1條邊把連通圖連接起來，并且使得權值的和最小，定義：把構造連通網的最小代價生成樹稱為最小生成樹，這里介紹兩種經典演算法，

1. 普里姆（Prim）演算法

假設N=(V,E)是連通圖，TE是N上的最小生成樹中邊的集合，

U={u0}(u0∈V)， TE={ }，

在所有u∈U，v∈V-U的邊(u，v)∈E 中找一條代價(權值)最小的邊(u0，v0) 并入集合TE，同時v0并入U，

重復2，直至U=V為止，
此時TE中必有n-1條邊，則T= (V,{TE}) 為N的最小生成樹，

python代碼實作：

class MGraph():
    def __init__(self):
        self.vertex = []
        self.matrix = []
        self.numNodes = 0
        self.numEdges = 0

    def createMGraph(self):
        """創建無向網圖的鄰接矩陣表示"""
        INFINITY = 65535
        self.numNodes = int(input("請輸入頂點數："))
        self.numEdges = int(input("請輸入邊數："))
        for i in range(self.numNodes):
            self.vertex.append(input("請輸入一個頂點："))

        for i in range(self.numNodes):
            self.matrix.append([])
            for j in range(self.numNodes):
                if i == j:
                    self.matrix[i].append(0)  # 初始化鄰接矩陣
                else:
                    self.matrix[i].append(INFINITY)  # 初始化鄰接矩陣

        for k in range(self.numEdges):  # 讀入numEdges條邊，建立鄰接矩陣
            i = int(input("請輸入邊(vi,vj)上的下標i:"))
            j = int(input("請輸入邊(vi,vj)上的下標j:"))
            w = int(input("請輸入邊(vi,vj)上的權w:"))
            self.matrix[i][j] = w
            self.matrix[j][i] = self.matrix[i][j]  # 因為是無向網圖，矩陣對稱

    def viewMGraphStruct(self):
        print(self.matrix)


def MiniSpanTree_Prim(G):
    INFINITY = 65535  # 用一個極大值代替∞
    adjvex = []  # 保存相關頂點間邊的權值點下標
    lowcost = []  # 保存相關頂點間邊的權值
    adjvex.append(0)  # 初始化第一個權值為0，即v0加入生成樹
    lowcost.append(0)  # 初始化第一個頂點下標為0，表示從v0開始
    for i in range(1, G.numNodes):  # 回圈除下標為0外的所有頂點
        lowcost.append(G.matrix[0][i])  # 將v0頂點與之有邊的權值存入串列
        adjvex.append(0)  # 初始化都為v0的下標
    for i in range(1, G.numNodes):
        min_w = INFINITY  # 初始化最小權值為∞
        j, k = 1, 0
        while j < G.numNodes:  # 回圈全部頂點
            if lowcost[j] != 0 and lowcost[j] < min_w:  # 如果權值不為0且權值小于min_w
                min_w = lowcost[j]  # 讓當前值成為最小值
                k = j  # 記錄最小值的下表，存入k
            j += 1
        print("({},{})".format(adjvex[k], k))  # 列印當前頂點邊中權值最小的邊
        lowcost[k] = 0  # 將當前頂點權值設為0，此頂點已完成任務
        for j in range(1,G.numNodes):  # 回圈所有頂點
            if lowcost[j] != 0 and G.matrix[k][j] < lowcost[j]:  # 如果下標為k的頂點的各邊權值小于此前這些頂點未被加入生成樹的權值
                lowcost[j] = G.matrix[k][j]  # 將較小的權值存入lowcost相應位置
                adjvex[j] = k  # 將下標為k的頂點存入adjvex


if __name__ == '__main__':
    G = MGraph()
    G.createMGraph()
    G.viewMGraphStruct()
    MiniSpanTree_Prim(G)

以下圖網圖為例：

輸入圖的資訊后生成的鄰接矩陣和最小生成樹如下所示：

[[0, 10, 65535, 65535, 65535, 11, 65535, 65535, 65535],
[10, 0, 18, 65535, 65535, 65535, 16, 65535, 12],
[65535, 18, 0, 22, 65535, 65535, 65535, 65535, 8], 
[65535, 65535, 22, 0, 20, 65535, 24, 16, 21],
[65535, 65535, 65535, 20, 0, 26, 65535, 7, 65535], 
[11, 65535, 65535, 65535, 26, 0, 17, 65535, 65535],
[65535, 16, 65535, 24, 65535, 17, 0, 19, 65535], 
[65535, 65535, 65535, 16, 7, 65535, 19, 0, 65535], 
[65535, 12, 8, 21, 65535, 65535, 65535, 65535, 0]]

(0,1)
(0,5)
(1,8)
(8,2)
(1,6)
(6,7)
(7,4)
(7,3)

演算法時間復雜度分析：有代碼中的回圈嵌套可以看出對于有n個頂點的無向網圖來說，演算法的時間復雜度為O(n²)

2. 克魯斯卡爾(Kruskal)演算法

假設連通網N=(V,E),將N中的邊按權值從小到大的順序排列，

初始狀態為只有n個頂點而無邊的非連通圖T={V，{ }}，圖中每個頂點自成一個連通分量，

在E 中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中(即不形成回路)，否則舍去此邊而選擇下一條代價最小的邊，

重復2，直至T中所有頂點都在同一個連通分量上為止，

演算法的實作要先將鄰接矩陣的存盤方式轉換為邊集陣列的存盤方式，

演算法步驟：

將鄰接矩陣的存盤方式轉換為邊集陣列的存盤方式，

將邊集陣列Edge中的元素按權值從小到大排序，

依次查看陣列Edge中的邊，回圈執行以下操作：

依次從排序好的陣列Edge中選出一條邊（U1,U2）

在Vexset中分別查找v1和v2 所在的連通分量vs1 和vs2，并進行判斷：

*如果vs1 和vs2不等，表明所選的兩個頂點分屬不同的連通分量，輸出此邊，并合并vs1 和vs2兩個連通分量，
*如果vs1 和vs2相等，表明所選的兩個頂點屬于同一個連通分量，舍去此邊而選擇下一條權值最小的邊，

python實作：

 class MGraph():
    def __init__(self):
        self.vertex = []
        self.matrix = []
        self.numNodes = 0
        self.numEdges = 0

    def createMGraph(self):
        """創建無向網圖的鄰接矩陣表示"""
        INFINITY = 65535
        self.numNodes = int(input("請輸入頂點數："))
        self.numEdges = int(input("請輸入邊數："))
        for i in range(self.numNodes):
            self.vertex.append(input("請輸入一個頂點："))

        for i in range(self.numNodes):
            self.matrix.append([])
            for j in range(self.numNodes):
                if i == j:
                    self.matrix[i].append(0)  # 初始化鄰接矩陣
                else:
                    self.matrix[i].append(INFINITY)  # 初始化鄰接矩陣

        for k in range(self.numEdges):  # 讀入numEdges條邊，建立鄰接矩陣
            i = int(input("請輸入邊(vi,vj)上的下標i:"))
            j = int(input("請輸入邊(vi,vj)上的下標j:"))
            w = int(input("請輸入邊(vi,vj)上的權w:"))
            self.matrix[i][j] = w
            self.matrix[j][i] = self.matrix[i][j]  # 因為是無向網圖，矩陣對稱

    def viewMGraphStruct(self):
        print(self.matrix)


class EdgeNode():
    """邊節點"""
    def __init__(self):
        self.begin = None
        self.end = None
        self.weight = None


def TransEdge(G):
    """將鄰接矩陣轉換為邊集陣列"""
    INFINITY = 65535  # 極大值
    k = 0
    edges = []  # 邊集陣列
    for i in range(G.numEdges):  # 注意這里千萬不要用串列推導式，初始化邊集陣列，不然會出現串列越界錯誤
        e = EdgeNode()  # 實體化邊節點
        edges.append(e)
    for i in range(G.numNodes - 1):
        for j in range(i + 1, G.numNodes):
            if 0 < G.matrix[i][j] < INFINITY:
                edges[k].begin = i
                edges[k].end = j
                edges[k].weight = G.matrix[i][j]
                k += 1
    # 按權由小到大排序(冒泡排序)
    for i in range(G.numEdges):
        for j in range(i + 1, G.numEdges):
            if edges[i].weight > edges[j].weight:
                edges[i], edges[j] = edges[j], edges[i]

    print("權排序后的為：")
    for i in range(G.numEdges):
        print("({},{}) {}".format(edges[i].begin, edges[i].end, edges[i].weight))

    return edges


def Find(parent, f):
    """查找連線頂點的尾部下標"""
    while parent[f] > 0:
        f = parent[f]
    return f


def MiniSpanTree_Kruskal(G):
    parent = [0 for _ in range(G.numNodes)]  # 定義并初始化一個串列用來判斷邊與邊是否形成環路
    edges = TransEdge(G)  # 由鄰接矩陣轉換來的邊集陣列
    print("列印最小生成樹：")
    for i in range(G.numEdges):  # 回圈每一條邊
        n = Find(parent, edges[i].begin)
        m = Find(parent, edges[i].end)
        if n != m:  # 如果n與m不相等，說明此邊沒有與現有的生成樹形成環路
            parent[n] = m  # 將此邊的結尾頂點放入下標為起點的的parent中，表示此頂點已經在生成樹集合中
            print("({},{}) {}".format(edges[i].begin, edges[i].end, edges[i].weight))


if __name__ == '__main__':
    G = MGraph()
    G.createMGraph()
    G.viewMGraphStruct()
    MiniSpanTree_Kruskal(G)

以下圖網圖為例：

輸入圖的資訊后生成的鄰接矩陣和最小生成樹如下所示：

[[0, 10, 65535, 65535, 65535, 11, 65535, 65535, 65535], 
[10, 0, 18, 65535, 65535, 65535, 16, 65535, 12], 
[65535, 18, 0, 22, 65535, 65535, 65535, 65535, 8],
[65535, 65535, 22, 0, 20, 65535, 24, 16, 21], 
[65535, 65535, 65535, 20, 0, 26, 65535, 7, 65535], 
[11, 65535, 65535, 65535, 26, 0, 17, 65535, 65535],
[65535, 16, 65535, 24, 65535, 17, 0, 19, 65535], 
[65535, 65535, 65535, 16, 7, 65535, 19, 0, 65535],
[65535, 12, 8, 21, 65535, 65535, 65535, 65535, 0]]

列印最小生成樹：
(4,7) 7
(2,8) 8
(0,1) 10
(0,5) 11
(1,8) 12
(3,7) 16
(1,6) 16
(6,7) 19

演算法時間復雜度分析：此演算法的Find函式由邊數e決定，時間復雜度為O(loge),而外面有一個for回圈e次，所以克魯斯卡爾演算法的時間復雜度為O(eloge)，對比兩個演算法，克魯斯卡爾演算法主要針對邊來展開，變數少時效率會非常高，所以對于稀疏圖有很大優勢，而普里姆演算法對于稠密圖，即邊數非常多的情況會更好一些，

本文部分概念和圖片來自：https://www.jianshu.com/p/d9ca383e2bd8

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/523109.html

標籤：其他

上一篇：1.2 宏處理函式

下一篇：游戲影片技術簡介