Python实现最小生成树算法详解（从零开始掌握Prim与Kruskal算法）

方法一：Prim算法（贪心策略）

Prim算法从一个起始顶点开始，逐步扩展生成树，每次选择与当前树相连且权重最小的边，直到包含所有顶点。它非常适合稠密图（边很多的图）。

下面是一个使用邻接矩阵实现Prim算法的Python代码：

import sysdef prim_mst(graph):    num_vertices = len(graph)    # selected[i] 表示顶点i是否已加入MST    selected = [False] * num_vertices    # 初始化：从顶点0开始    selected[0] = True    edge_count = 0    total_weight = 0        print("边\t\t权重")    while edge_count < num_vertices - 1:        minimum = sys.maxsize        x = y = -1                # 遍历所有已选顶点        for i in range(num_vertices):            if selected[i]:                # 寻找连接未选顶点的最小权重边                for j in range(num_vertices):                    if not selected[j] and graph[i][j] != 0:                        if graph[i][j] < minimum:                            minimum = graph[i][j]                            x, y = i, j                if x != -1 and y != -1:            print(f"{x} - {y}\t\t{graph[x][y]}")            selected[y] = True            total_weight += graph[x][y]            edge_count += 1        print(f"最小生成树总权重: {total_weight}")    return total_weight# 示例图（邻接矩阵表示）graph = [    [0, 2, 0, 6, 0],    [2, 0, 3, 8, 5],    [0, 3, 0, 0, 7],    [6, 8, 0, 0, 9],    [0, 5, 7, 9, 0]]prim_mst(graph)

方法二：Kruskal算法（基于并查集）

Kruskal算法采用不同的思路：它将所有边按权重从小到大排序，然后依次选择边，只要不形成环就加入生成树。该算法依赖并查集（Union-Find）数据结构来高效检测环。

以下是Kruskal算法的Python实现：

class UnionFind:    def __init__(self, n):        self.parent = list(range(n))        def find(self, x):        if self.parent[x] != x:            self.parent[x] = self.find(self.parent[x])  # 路径压缩        return self.parent[x]        def union(self, x, y):        root_x = self.find(x)        root_y = self.find(y)        if root_x != root_y:            self.parent[root_x] = root_y            return True        return Falsedef kruskal_mst(vertices, edges):    # edges 格式: [(weight, u, v), ...]    edges.sort()  # 按权重升序排序    uf = UnionFind(vertices)    mst_edges = []    total_weight = 0        for weight, u, v in edges:        if uf.union(u, v):  # 如果不形成环            mst_edges.append((u, v, weight))            total_weight += weight            if len(mst_edges) == vertices - 1:                break        print("最小生成树的边及权重：")    for u, v, w in mst_edges:        print(f"{u} - {v}: {w}")    print(f"总权重: {total_weight}")    return total_weight# 示例：5个顶点，边列表edges = [    (2, 0, 1),    (3, 1, 2),    (5, 1, 4),    (6, 0, 3),    (7, 2, 4),    (8, 1, 3),    (9, 3, 4)]kruskal_mst(5, edges)

Prim vs Kruskal：如何选择？

• Prim算法适合稠密图（边数接近顶点数平方），时间复杂度为 O(V²)，使用优先队列可优化至 O(E log V)。
• Kruskal算法适合稀疏图（边数远小于顶点数平方），时间复杂度为 O(E log E)，主要开销在排序。

总结

通过本教程，你已经掌握了使用Python实现最小生成树算法的核心方法。无论是Prim还是Kruskal，它们都体现了图论算法中“贪心”思想的巧妙应用。建议你动手运行上述代码，修改图的结构，观察输出结果，加深理解。

掌握这些基础算法，不仅能帮你解决实际工程问题，也是面试中常见的考点。希望这篇教程能成为你学习Python最小生成树的起点！