最小生成树在生活中可以运用到许多实际的问题。例如在n个城市之间建立通信网络，很容易知道至少要架设n-1条线路，每条线路可能因为路程、地势等多方面原因，造价可能也不同，怎么设计出造价最小的线路，并且使每个城市都互联。最小生成树就能给出答案。
下面我们来看看最小生成树的两种经典算法。
Prim（普里姆）算法：（割边）
PRIM算法 基本思想：
（V代表定点，E代表边）假设N=(V,{E})是联通网，TE是N上的最想生成树中的变得集合。算法从 U={u0}(u0属于V)，TE={}开始，重复执行下述操作：在所有的u属于U，v属于V-U的边（u，v）属于E中找到一条代价最小的（u0，v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,{TE}) 为N的最小生成树。
下面我们用一张图就能很清楚的了解Prim算法的思想。
（1）首先将A结点加入到集合，取权值最小的边（19）将F连接起来，割掉其他边；
（2）再将F加入集合，取除了与A相连的另外几条最小的边，这里权值最小边有两条（25），选择其中一条（与C结点相连的边），并割掉其他边；
（3）重复以上步骤，直到所有的顶点都加入到集合中。从而形成的就是这个图权重最小的情况。
当然最小生成树并不唯一。
Kruskal（克鲁斯卡尔）算法： （加边）
Kruskal的基本思想：
克鲁斯卡尔算法从另一个途径求网中的最小生成树。假设联通网N=(V,{E})，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个顶点各自构成一个连通分量。 在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条最小的边。以此类推，直至T中所有的顶点都在同一连通分量上为止。
我们同样用一张图来了解Kruskal的基本思想。
kruskal 首先将所有的边都去掉，然后再所有边中找到权重最小的边，并将两个连通分量连接成一个，就把边加入到集合。这里第一次边的权重最小的是1，将权重为1所在的边的顶点连接，形成一个连通分量。接着最小边依然是1，并且能将两个连通分量连接成一个连通分量，所以在此把1所在的边加上。以此类推，知道形成一个连通分量为止。
简单实现。读者可以简单琢磨一下，里面注释比较详细：
package org.TT.MST;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
/**
* 图的最小树生成算法
*/
public class MiniSpanTree {
/**
* @param graph 图
* @param start 开始节点
* @param n 图中节点数
*/
public static void PRIM(int[][] graph, int start, int n) {
/*mins 用于保存集合U到V-U之间的最小边和它的值，
mins[i][0]值表示到该节点i边的起始节点,值为-1表示没有到它的起始点
mins[i][1]值表示到该边的最小值，
mins[i][1]=0表示该节点已将在集合U中 */
int[][] mins = new int[n][2];
for (int i = 0; i < n; i++) {// 初始化mins
System.out.println("初始化mins[][]:");
if (i == start) {
mins[i][0] = -1;
mins[i][1] = 0;
} else if (graph[start][i] != -1) {// 说明存在（start，i）的边
mins[i][0] = start;
mins[i][1] = graph[start][i];
} else {
mins[i][0] = -1;
mins[i][1] = Integer.MAX_VALUE;
}
System.out.println("mins[" + i + "][0]=" + mins[i][0] + "||mins["
+ i + "][1]=" + mins[i][1]);
}
for (int i = 1; i < n; i++) {
int minV = -1, minW = Integer.MAX_VALUE; // minV 保存新加入U 集合的节点
for (int j = 0; j < n; j++) {// 找到mins中最小值，使用O(n^2)时间
if (mins[j][1] != 0 && minW > mins[j][1]) {
minW = mins[j][1];
minV = j;
}
}
System.out.println("minV=" + minV); // 新加入 U 的节点 顺序为 V0 -> V2 -> V5
// -> V3 -> V1 -> V4
mins[minV][1] = 0;
System.out.println("最小生成树的第" + i + "条最小边=<" + (mins[minV][0]) + ","
+ (minV) + ">，权重=" + minW);
for (int j = 0; j < n; j++) {// 更新mins数组
if (mins[j][1] != 0) { // 判断节点是否在集合U里面，等于0 表示在集合U里面
// System.out.println("MINV="+minV+"||tree[minV][j]="+tree[minV][j]);
if (graph[minV][j] != -1 && graph[minV][j] < mins[j][1]) {
mins[j][0] = minV;
mins[j][1] = graph[minV][j];
}
}
}
// 输出更新后的mins[][];
System.out.println("每次更新后的mins[][]数组：");
for (int k = 0; k < 6; k++) {
System.out.println("mins[" + k + "][0]=" + mins[k][0]
+ "||mins[" + i + "][1]=" + mins[k][1]);
}
}
// 输出最后调整的mins[][];
System.out.println("最后的mins[][]");
for (int i = 0; i < 6; i++) {
System.out.println("mins[" + i + "][0]=" + mins[i][0] + "||mins["
+ i + "][1]=" + mins[i][1]);
}
}
/**
* @param V 图中的节点集合
* @param E 图中边的集合
*/
@SuppressWarnings({ "rawtypes", "unchecked" })
public static void KRUSKAL(int[] V, Edge[] E) {
Arrays.sort(E);// 将边按照权重w升序排序
System.out.println("按权重排序后的边：");
for(Edge e: E){
System.out.println(e);
}
ArrayList<HashSet> sets = new ArrayList<HashSet>();
for (int i = 0; i < V.length; i++) {//将顶点全部存放于数组中
HashSet<Integer> set = new HashSet<Integer>();
set.add(V[i]);
sets.add(set);
}
System.out.println("++++++++++++++++++++++顶点数size=" + sets.size());
for (int i = 0; i < E.length; i++) {
int start = E[i].i, end = E[i].j;
int counti = -1, countj = -2;
//在各个连通分量中查找是否含有起始和终止顶点，有并返回顶点的连通分量位置
for (int j = 0; j < sets.size(); j++) {
HashSet set = sets.get(j);
if (set.contains(start)) {
counti = j;
}
if (set.contains(end)) {
countj = j;
}
}
if (counti < 0 || countj < 0)
System.err.println("没有在子树中找到节点，错误");
System.out.println("顶点位置：counti = " + counti + " countj = " + countj);
if (counti != countj) { //表示顶点位于两个不同的连通分量
System.out.println("输出start=" + start + "||end=" + end + "||w="
+ E[i].w);
HashSet<Integer> setj = sets.get(countj);
//移除有边的两个连通分量，并将这两个连通组合在一起，合并为一个大的连通分量，存储在sets集合中
sets.remove(countj);
HashSet<Integer> seti = sets.get(counti);
sets.remove(counti);
seti.addAll(setj);
sets.add(seti);
} else {
System.out.println("他们在一棵子树中，不能输出start=" + start + "||end="
+ end + "||w=" + E[i].w);
}
}
}
//第一趟 setj = [3] seti = [1,3] sets = [[2], [4], [5], [6], [1, 3]] 顶点1,3(权重为：1)连通
//第二趟 setj = [6] seti = [4,6] sets = [[2], [5], [1, 3], [4, 6]] 顶点4,6(权重为：2)连通
//第三趟 setj = [5] seti = [2,5] sets = [[1, 3], [4, 6], [2, 5]] 顶点2,5(权重为：3)连通
//第四趟 setj = [4,6] seti = [1,3,4,6] sets = [[2, 5], [1, 3, 4, 6]]
//顶点3和6所在的连通分量(权重为：4)连通顶点1和4连通(权重为：5),由于1,4已经连通(已经在一个集合),所以不输出
//第五趟 setj = [1,3,4,6] seti = [1,2,3,4,5,6] sets = [[1, 2, 3, 4, 5, 6]] 顶点2和3所在的连通分量(权重为：5)连通
public static void main(String[] args) {
int[][] tree = {
{ -1, 6, 1, 5, -1, -1 },
{ 6, -1, 5, -1, 3, -1 },
{ 1, 5, -1, 5, 6, 4 },
{ 5, -1, 5, -1, -1, 2 },
{ -1, 3, 6, -1, -1, 6 },
{ -1, -1, 4, 2, 6, -1 } };
System.out.println("+++++++++++++++++++++++++++++++++ Prim（普里姆）算法");
MiniSpanTree.PRIM(tree, 0, 6);
System.out.println("+++++++++++++++++++++++++++++++++ Kruskal（克鲁斯卡尔）算法");
int[] V = { 1, 2, 3, 4, 5, 6 };
Edge[] E = new Edge[10];
E[0] = new Edge(1, 2, 6);
E[1] = new Edge(1, 3, 1);
E[2] = new Edge(1, 4, 5);
E[3] = new Edge(2, 3, 5);
E[4] = new Edge(2, 5, 3);
E[5] = new Edge(3, 4, 5);
E[6] = new Edge(3, 5, 6);
E[7] = new Edge(3, 6, 4);
E[8] = new Edge(4, 6, 2);
E[9] = new Edge(5, 6, 6);
MiniSpanTree.KRUSKAL(V, E);
}
}