【1】什么是最小生成树？
对于连通的带权图(连通网)G，其生成树也是带权的。
生成树T各边的权值总和称为该树的权。
权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。简记为MST。
注意：最小是指权值最小
一个连通图的生成树是一个极小的连通子图，它包含全部的顶点，但只有足以构成一棵树的n-1条边。
求最小生成树有两种算法：普里姆算法和克鲁斯卡尔算法 最小代价生成树，都是针对无向图
不好理解？看不懂？能通俗点不？看个实例哈：
假设你是电信实施工程师，需要为一个镇的九个村庄架设通信网络做设计。
村庄位置大致如下图，之间连线的数字表示村与村间的可通达直线距离。
你们领导要求你必须用最小的成本完成这次任务。你说怎么办？
好，这就是很现实的一个最小生成树案例。且听下面详解。
【2】普里姆算法
利用 普里姆算法 要解决如上问题，首先我们构造图的邻接矩阵。如下图所示：
注意：实际中我们用65535来代表无穷大。
关于普里姆算法以及讲解如下图：
针对上面我们遇到的实际案例，普里姆算法执行循环过程如下图：
每次所选最小边分别如 图1-图8 所示：
最后用所有边把各个顶点连通也就是所谓的最小生成树。
【3】普里姆算法的实现
实现代码如下：
/**
* 最小生成树：两种方式，普里姆算法和克鲁斯卡尔算法
* @author timmy1
*
*/
public class MinSpanTree {
int[][] matrix;// 矩阵
int MAX_WEIGHT = Integer.MAX_VALUE;
int size;// 顶点个数
/**
* 普里姆算法实现最小生成树：先初始化拿到第一个顶点相关联的权值元素放到数组中－》找到其中权值最小的顶点下标－》再根据该下标，将该下标顶点相关联的权值加入到数组中－》循环遍历处理
*/
public void prim(){
int[] tempWeight = new int[size];// 临时存放顶点权值的数组，每次循环都要从中获取到最小权值和顶点下标
int minWeight;//最小权值
int minId;//最小权值顶点
int sum = 0;//权值总和
//先初始化将第一行的顶点权值存放到临时权值数组中
for(int i =0;i<size;i++){
tempWeight[i] = matrix[0][i];
}
PrintUtil.print("从顶点0开始查找");
for(int i=1;i<size;i++){
//每次循环都找出临时顶点权值的最小的权值
minWeight = MAX_WEIGHT;
minId = 0;
for(int j=1;j<size;j++){
if(tempWeight[j] >0 && tempWeight[j]<minWeight){
minWeight = tempWeight[j];
minId = j;
}
}
//找到目标顶点minId,他的权值为minweight。
PrintUtil.print("找到顶点:"+minId+" 权值为："+minWeight);
sum+=minWeight;
//根据找到的顶点minid，将这一行的所有相关联的顶点权值添加到临时权值数组中
tempWeight[minId] = 0;
for(int j = 1;j<size;j++){
if(tempWeight[j] != 0&& matrix[minId][j]<tempWeight[j]){
tempWeight[j] = matrix[minId][j];
}
}
}
PrintUtil.print("最小权值总和为："+sum);
}
private void createGraph(int index) {
size = index;
matrix = new int[index][index];
int[] a0 = { 0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
int[] a1 = { 10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12 };
int[] a2 = { MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8 };
int[] a3 = { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, 24, 16, 21 };
int[] a4 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT };
int[] a5 = { 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT };
int[] a6 = { MAX_WEIGHT, 16, MAX_WEIGHT, 24, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT };
int[] a7 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT };
int[] a8 = { MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0 };
matrix[0] = a0;
matrix[1] = a1;
matrix[2] = a2;
matrix[3] = a3;
matrix[4] = a4;
matrix[5] = a5;
matrix[6] = a6;
matrix[7] = a7;
matrix[8] = a8;
}
public static void main(String[] args) {
MinSpanTree graph = new MinSpanTree();
graph.createGraph(9);
graph.prim();
}
}