最小生成樹-Kruskal算法

Kruskal算法

更為直接地貪心，每次從圖中找：

沒有收錄的

不會構成回路的

權重最小的邊

class Edge:
    def __init__(self, weight=None, v1=None, v2=None):
        self.weight = weight
        self.v1 = v1
        self.v2 = v2
    def __lt__(self, other): # 比較類的對象比其他小的
        return self.weight < other.weight
class MSTNode:
    def __init__(self,v1=None,v2=None):
        self.v1 = v1
        self.v2 = v2
graph = {
    1:{2:2,4:1,3:4},
    2:{5:10,4:3,1:2},
    3:{1:4,6:5,4:2},
    4:{3:2,6:8,7:4,5:7,2:3,1:1},
    5:{7:6,2:10,4:7},
    6:{7:1,4:8,3:5},
    7:{6:1,4:4,5:6},
}
INFINITY = float('inf')
# 轉化為二維矩陣表示圖，兩點不鄰接用無窮大表示
graph = [[graph[v1].get(v2,INFINITY) for v2 in graph] for v1 in graph]
           

class SetADT:
    def __init__(self):
        self.set = list()  # 預設集合初始元素為-1 
    def find(self, target):
        if self.set[target] < 0:  # 找到集合的根
            return target
        else:
            # 先找到根，把根變成x的父結點，再傳回根
            self.set[target] = self.find(self.set[target]) # 路徑壓縮
            return self.set[target]
    def union(self, par1=None, par2=None):
        if self.set[par1] < self.set[par2]:  # 按秩歸并
            self.set[par1] += self.set[par2]
            self.set[par2] = par1
        else:
            self.set[par2] += self.set[par1]
            self.set[par1] = par2
           

from heapq import *
def InitEdge(graph):
    EdgeSet = list()
    for row in range(len(graph)):
        for col in range(row+1,len(graph[row])): # 避免重複錄入無向圖的邊，隻收單向邊，取上三角矩陣，不包括對角線
            if graph[row][col] < INFINITY:
                EdgeSet.append(Edge(graph[row][col],row,col))
    heapify(EdgeSet) # 生成最小堆
    return EdgeSet
def CheckCircle(VertexSet,v1,v2): # 檢查連接配接V1和V2的邊是否在現有的最小生成樹子集中構成回路
    root1 = VertexSet.find(v1) # 得到V1所屬的連通集名稱
    root2 = VertexSet.find(v2) # 得到V2所屬的連通集名稱
    if root1 == root2: # 若V1和V2已經連通，則該邊不能要
        return False
    else: # 否則該邊可以被收集，同時将V1和V2并入同一連通集
        VertexSet.union(root1,root2)
        return True
def Kruskal(graph):
    VertexSet = SetADT()
    VertexSet.set = [-1 for i in range(len(graph))] # 初始化頂點集合
    EdgeSet = InitEdge(graph)
    MST = list()
    TotalWeight = 0
    EdgeCount = 0
    while EdgeCount < len(graph)-1: # 一共要找V-1條邊
        next_edge = heappop(EdgeSet) # 從邊集中得到最小邊
        if next_edge is None:
            break
        if CheckCircle(VertexSet,next_edge.v1,next_edge.v2):
            # 如果該邊的加入不構成回路，即兩端結點不屬于同一連通集
            MST.append(MSTNode(next_edge.v1+1,next_edge.v2+1)) # 将該邊插入MST，由于集合定義從下标為0開始，是以這裡要＋1
            TotalWeight += next_edge.weight
            EdgeCount += 1
    if EdgeCount < len(graph)-1: # 當MST的邊數＜V-1時，說明圖不是連通的
        TotalWeight = None
    return TotalWeight
           

各鄰接點:

6 - 7

1 - 4

3 - 4

1 - 2

4 - 7

5 - 7

MST : 集合根結點為4,樹規模為7

[3, 3, 3, -7, 3, 3, 3]

樹的權重: 16