克鲁斯卡尔最小生成树的伪代码

### Kruskal 最小生成树算法伪代码

Kruskal 算法通过逐步添加权重最小的边来构建最小生成树，前提是这些边不会形成环路。以下是详细的伪代码：

function kruskalMST(graph):
    edges = graph.getAllEdges()  # 获取所有边
    sort(edges, by=weight)       # 按照边的权重升序排列
    
    disjointSet = makeDisjointSets(vertices)  # 初始化不相交集合（并查集）
    
    minimumSpanningTree = []     # 存储最终的最小生成树
    totalWeight = 0              # 记录总权重

    for each edge (u, v, weight) in edges:
        if find(disjointSet, u) != find(disjointSet, v):  # 如果两个端点不在同一个集合内，则加入这条边
            union(disjointSet, u, v)                      # 合并这两个节点所在的集合
            add edge to minimumSpanningTree               # 将此条边加入到最小生成树中
            totalWeight += weight                         # 更新当前已选路径长度
            
    return minimumSpanningTree, totalWeight             # 返回最小生成树及其总重量

上述实现利用了贪心策略，在每一步都选择局部最优解——即连接两棵树之间的最短边，从而保证全局最优解。

为了提高效率，通常会采用按秩合并和路径压缩技术优化 `find` 和 `union` 操作[^1]。