最小支撑树是一个无向连通图的生成树，它包含了该图的所有节点且边的总权值最小。求解最小支撑树的经典算法是Prim算法和Kruskal算法。
Prim算法从一个起始节点开始，每次添加一个与当前集合相邻且权值最小的节点，直到所有节点都被加入。
Kruskal算法则是从所有边中选择权值最小的边，如果这条边不会导致环的出现，就将它加入生成树，直到所有节点都被加入。
证明最小支撑树的正确性需要用到割定理，即对于任意划分的点集，最小割等于最小支撑树的权值。
求解最小支撑树的常见算法有普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。
1. 普里姆算法：
- 选择一个起始顶点作为根节点，并将其加入最小支撑树中。
- 通过贪心策略，每次从已经加入最小支撑树的顶点集合中选择一个顶点v，并从与v相邻的未加入树的顶点集合中选择一条权重最小的边(u, v)。
- 将边(u, v)加入最小支撑树，并将顶点v加入已加入树的顶点集合中。
- 重复上述步骤，直到所有的顶点都加入了最小支撑树。
普里姆算法的正确性证明如下：
- 首先，我们要证明最初生成的树是一个连通树。因为我们从一个起始顶点开始，每次选择的边连接已加入树的顶点集合和未加入树的顶点集合，所以树始终保持连通。
- 其次，我们要证明最小支撑树的权重确实是最小的。假设存在另一棵权重更小的树T'，则根据贪心策略，我们可以交换T'中某条边和最小支撑树中对应的边，使得总权重更小。这与最小支撑树的定义相矛盾，因此最小支撑树的权重是最小的。
2. 克鲁斯卡尔算法：
- 将图中的所有边按照权重从小到大进行排序。
- 从权重最小的边开始，依次将边加入最小支撑树中，如果加入该边不会构成回路，则将其加入树中。
- 重复上述步骤，直到最小支撑树中包含了图中的所有顶点。
克鲁斯卡尔算法的正确性证明如下：
- 首先，我们要证明最终生成的树是一个连通树。在每一步中，我们选择的边不会构成回路，因此每次加入一条边都会将两个不同的连通分量连接起来，直到最终生成一个连通树。
- 其次，我们要证明最小支撑树的权重确实是最小的。假设存在另一棵权重更小的树T'，则根据排序的顺序，我们可以找到T'中某条边(e')，该边在排序中先于当前考虑的边(e)。由于克鲁斯卡尔算法始终选择权重最小的边，所以T'中的边(e')一定比(e)更早加入树中。那么我们可以交换(e')和(e)，将(e')从T'中移除并替换为(e)，最终生成的树仍然是连通的且权重更小。这与T'是最小支撑树的假设相矛盾，因此最小支撑树的权重是最小的。
总结起来，普里姆算法和克鲁斯卡尔算法都通过贪心策略逐步构建最小支撑树，并且都能保证得到最小权重的树。具体选择哪种算法取决于问题的特点和数据规模。
