最小生成树算法python

Python 中有多种实现最小生成树算法的方法，最常用的两种是 Kruskal 算法和 Prim 算法。

以下是 Kruskal 算法的 Python 实现：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []
  
    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])
  
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])
  
    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
  
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1
  
    def kruskal_mst(self):
        result = []
        i = 0
        e = 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []
        for node in range(self.V):
            parent.append(node)
            rank.append(0)
  
        while e < self.V - 1:
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)
  
            if x != y:
                e = e + 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)
  
        minimum_cost = 0
        for u, v, weight in result:
            minimum_cost += weight
        return minimum_cost

以下是 Prim 算法的 Python 实现：

import sys
  
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]
  
    def print_mst(self, parent):
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])
  
    def min_key(self, key, mst_set):
        min = sys.maxsize
        for v in range(self.V):
            if key[v] < min and mst_set[v] == False:
                min = key[v]
                min_index = v
        return min_index
  
    def prim_mst(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V 
        key[0] = 0
        mst_set = [False] * self.V
  
        parent[0] = -1
  
        for cout in range(self.V):
            u = self.min_key(key, mst_set)
            mst_set[u] = True
  
            for v in range(self.V):
                if self.graph[u][v] > 0 and mst_set[v] == False and key[v] > self.graph[u][v]:
                        key[v] = self.graph[u][v]
                        parent[v] = u
  
        return self.print_mst(parent)

这两种算法的时间复杂度都是 O(ElogV)，其中 E 是边数，V 是顶点数。