最小代价生成树

最小代价生成树（MCST）连接图中所有顶点，使边权总和最小，Prim 算法适合稠密图，Kruskal 适合稀疏图。

定义与用途

最小代价生成树（Minimum Cost Spanning Tree, MCST）是加权无向图中连接所有顶点的无环子图，边权总和最小。

应用场景：

领域	用途
网络设计	电信、计算机网络布线优化
城市规划	道路、桥梁建设成本最小化
集群分析	数据点相似性识别
图像处理	图像分割与对象识别

Prim 算法

从顶点出发，逐步扩展生成树。适用于稠密图。

算法步骤：

1. 任选起始顶点
2. 找连接生成树与未选顶点的最小边
3. 重复直到覆盖所有顶点

import sys
 
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0] * vertices for _ in range(vertices)]
 
    def primMST(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[0] = 0
        mstSet = [False] * self.V
 
        for _ in range(self.V):
            u = min((key[v], v) for v in range(self.V) if not mstSet[v])[1]
            mstSet[u] = True
            for v in range(self.V):
                if self.graph[u][v] > 0 and not mstSet[v] and key[v] > self.graph[u][v]:
                    key[v], parent[v] = self.graph[u][v], u
 
        for i in range(1, self.V):
            print(f"{parent[i]} - {i}: {self.graph[i][parent[i]]}")
 
# 示例
g = Graph(5)
g.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]]
g.primMST()

Kruskal 算法

从边出发，按权值排序后贪心选择。适用于稀疏图。

算法步骤：

1. 按权值排序所有边
2. 依次选择不形成环的边
3. 直到生成树包含所有顶点

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []
 
    def addEdge(self, u, v, w):
        self.graph.append([u, v, w])
 
    def find(self, parent, i):
        return i if parent[i] == i else self.find(parent, parent[i])
 
    def kruskalMST(self):
        self.graph.sort(key=lambda x: x[2])
        parent, rank = list(range(self.V)), [0] * self.V
        result = []
 
        for u, v, w in self.graph:
            x, y = self.find(parent, u), self.find(parent, v)
            if x != y:
                result.append([u, v, w])
                parent[y] = x if rank[x] > rank[y] else y
                if rank[x] == rank[y]:
                    rank[x if parent[y] == x else y] += 1
 
        for u, v, w in result:
            print(f"{u} - {v}: {w}")
 
# 示例
g = Graph(4)
g.addEdge(0,1,10), g.addEdge(0,2,6), g.addEdge(0,3,5), g.addEdge(1,3,15), g.addEdge(2,3,4)
g.kruskalMST()

时间复杂度：Prim 为 O(V²)，Kruskal 为 O(E log E)。