数据结构用破圈法求最小生成树

破圈法，也称为Prim算法或Prim-Moore算法，是一种用于寻找无向加权图中最小生成树（Minimum Spanning Tree, MST）的贪心算法。在Prim算法中，我们从一个初始顶点开始，逐步添加边，每一步都选择当前图中与已选顶点集合相连、并且权重最小的一条边，直到所有顶点都被包含在内。

以下是破圈法求最小生成树的基本步骤：

1. 初始化：选择图中的任意一个顶点作为起点，并将其标记为已访问。设置一个集合，包含起点，形成初始的最小生成树。

2. 扩展阶段：对于图中尚未访问的所有顶点，计算它们到已访问顶点集合中所有顶点的最短边（权重）。选择权重最小的边，但这条边不能形成一个环（如果这条边将已经形成的环封闭，则排除）。

3. 更新最小生成树：将这条新边的另一端加入到已访问顶点集合中，并更新最小生成树。

4. 重复步骤2和3，直到所有顶点都被访问过。此时，剩余的边中没有一条能进一步减少最小生成树的总权重，算法结束。