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

什么是“最小生成树”？

假设你有一个带权无向连通图（即任意两点之间都有路径可达），最小生成树就是从这个图中选出一棵包含所有顶点的树，使得这棵树的所有边的权重之和最小。

注意：生成树必须满足两个条件：

• 包含图中的所有顶点；
• 边数 = 顶点数 - 1，且不能有环。

方法一：Prim算法（普里姆算法）

Prim算法是一种贪心算法。它从一个起始顶点开始，每次选择连接已选顶点集合和未选顶点集合之间权重最小的边，直到所有顶点都被包含进来。

Prim算法适合用在稠密图（边很多）中，时间复杂度为 O(V²)，如果使用优先队列（堆）优化，可降至 O(E log V)。

Python实现Prim算法

import sysdef prim_mst(graph):    num_vertices = len(graph)    # selected[i] 表示顶点 i 是否已被选入MST    selected = [False] * num_vertices    # 初始化：从顶点0开始    selected[0] = True    mst_edges = []    total_weight = 0        for _ in range(num_vertices - 1):        minimum = sys.maxsize        u, v = -1, -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]                            u, v = i, j                if u != -1 and v != -1:            selected[v] = True            mst_edges.append((u, v, minimum))            total_weight += minimum        return mst_edges, 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]]edges, weight = prim_mst(graph)print("Prim算法得到的最小生成树边：", edges)print("总权重：", weight)

方法二：Kruskal算法（克鲁斯卡尔算法）

Kruskal算法也是一种贪心策略，但它按边的权重从小到大排序，依次选择边，只要加入该边不会形成环，就将其加入MST。

Kruskal算法适合稀疏图（边较少），时间复杂度主要由排序决定：O(E log E)，通常写作 O(E log V)。

实现Kruskal算法需要借助并查集（Union-Find）数据结构来高效判断是否成环。

Python实现Kruskal算法

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        return mst_edges, 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)]mst, weight = kruskal_mst(5, edges)print("Kruskal算法得到的最小生成树边：", mst)print("总权重：", weight)

总结对比

无论你是学习Python最小生成树、准备面试，还是解决实际工程问题，掌握Prim算法和Kruskal算法都是图论算法中的基础技能。希望这篇教程能帮助你轻松入门！

如果你觉得有用，不妨动手运行代码，修改图的结构，观察输出结果，加深理解。