用python实现最小生成树

在Python中实现最小生成树（Minimum Spanning Tree, MST），我们可以使用多种算法，如Prim算法和Kruskal算法。这里分别给出这两个算法的基本示例：

**Prim算法**：

import heapq

class Edge:
    def __init__(self, weight, node):
        self.weight = weight
        self.node = node

class Graph:
    def __init__(self, adj_list):
        self.adj_list = adj_list

    def prim_mst(self):
        vertices = set(range(len(self.adj_list)))
        mst_set = []
        dist = {i: float('inf') for i in vertices}
        dist = 0
        heap = [(0, 0)]

        while heap:
            current_weight, current_node = heappop(heap)
            if current_weight > dist[current_node]:
                continue

            vertices.remove(current_node)

            for neighbor, weight in self.adj_list[current_node].items():
                if neighbor in vertices and weight < dist[neighbor]:
                    dist[neighbor] = weight
                    heappush(heap, (weight, neighbor))

            mst_set.append((current_node, current_weight))

        return mst_set, sum(dist.values())

# 示例：
adj_list = [[0, 4], [4, 0], [4, 8], [4, 11], [11, 15]]
graph = Graph(adj_list)
mst, total_cost = graph.prim_mst()

**Kruskal算法**：

class Edge:
    def __init__(self, weight, from_node, to_node):
        self.weight = weight
        self.from_node = from_node
        self.to_node = to_node

class Graph:
    def __init__(self, adj_matrix):
        self.adj_matrix = adj_matrix

    def kruskal_mst(self):
        edges = [Edge(row[i], i, j) for i in range(len(adj_matrix)) for j, val in enumerate(adj_matrix[i]) if i != j]
        edges.sort(key=lambda e: e.weight)
        uf = UnionFind(len(adj_matrix))
        mst = []

        for edge in edges:
            if not uf.is_connected(edge.from_node, edge.to_node):
                uf.union(edge.from_node, edge.to_node)
                mst.append(edge)

        return mst

# 示例：
adj_matrix = [
    [0, 4, 0, 0],
    [4, 0, 8, 0],
    [0, 8, 0, 11],
    [0, 0, 11, 0]
]
graph = Graph(adj_matrix)
mst = graph.kruskal_mst()