用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_parent(self, parent, i):
        if parent[i] == i:
            return i
        return self.find_parent(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find_parent(parent, x)
        yroot = self.find_parent(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(parent, u)
            y = self.find_parent(parent, v)

            # 如果加入该边不会形成环，则加入最小生成树
            if x != y:
                e = e + 1
                result.append((u, v, w))
                self.union(parent, rank, x, y)

        return result


def min_spanning_tree(vertices, edges):
    graph = Graph(vertices)
    for edge in edges:
        graph.add_edge(edge[0], edge[1], edge[2])
    mst = graph.kruskal_mst()
    return mst


if __name__ == "__main__":
    vertices = 5
    edges = [
        (0, 1, 2),
        (0, 3, 6),
        (1, 4, 4),
        (1, 2, 5),
        (2, 4, 3),
        (3, 2, 8),
        (3, 4, 7)
    ]

    mst = min_spanning_tree(vertices, edges)
    print("最小生成森林：")
    for edge in mst:
        print(edge[0], "-", edge[1], ":", edge[2])