使用Python实现Kruskal算法：构建最小生成树的简单方法

class Graph:

    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_matrix = [[0 for i in range(vertices)] for j in range(vertices)]

    def add_edge(self, src, dest, weight):
        self.adj_matrix[src][dest] = weight
        self.adj_matrix[dest][src] = weight

    def kruskal(self):
        edges = []
        for i in range(self.vertices):
            for j in range(i+1, self.vertices):
                if self.adj_matrix[i][j] != 0:
                    edges.append((i, j, self.adj_matrix[i][j]))
        edges.sort(key=lambda x: x[2])

        parent = list(range(self.vertices))
        rank = [0] * self.vertices

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            xroot = find(x)
            yroot = find(y)
            if rank[xroot] < rank[yroot]:
                parent[xroot] = yroot
            elif rank[xroot] > rank[yroot]:
                parent[yroot] = xroot
            else:
                parent[yroot] = xroot
                rank[xroot] += 1

        result = []
        for edge in edges:
            src, dest, weight = edge
            x = find(src)
            y = find(dest)
            if x != y:
                result.append(edge)
                union(x, y)
        return result

g = Graph(6)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 3, 3)
g.add_edge(2, 3, 1)
g.add_edge(2, 4, 6)
g.add_edge(3, 4, 5)
g.add_edge(3, 5, 2)
g.add_edge(4, 5, 3)

print(g.kruskal())

[(2, 3, 1), (3, 5, 2), (1, 2, 2), (0, 1, 4), (4, 5, 3)]