概念
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。
在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。
3.png
最小生成树其实是最小权重生成树的简称。
应用场景
是在工程上解决问题。
例如：城市与城市之间的路程，从一个城市到达另一个城市需要经过其他的城市，那么如何以最短的路径到达，这就需要找到带权的最小生成树来解决。
Kruskal算法实现
/**
* 最小生成树，克鲁斯卡尔（kruskal）算法
* author: bobo
* create time: 2019/1/21 3:58 PM
* email: jqbo84@163.com
*/
public class Kruskal {
public int verticeSize;// 顶点的大小
public int[][] matrix; // 邻接矩阵
public int edgeSize; //边的大小
public Edge[] edges;
public static final int I = 0xFFF8;
public void init(int[][] matrix) {
this.matrix = matrix;
this.verticeSize = matrix.length;
}
/**
* 获取所有的边
*
* @return
*/
private Edge[] getEdges() {
int index = 0;
Edge[] edges = new Edge[verticeSize * verticeSize];
for (int i = 0; i < verticeSize; i++) {
for (int j = 0; j < verticeSize; j++) {
if (matrix[i][j] != 0 && matrix[i][j] != I) {
edges[index++] = new Edge(i, j, matrix[i][j]);
}
}
}
edgeSize = index;
return edges;
}
/**
* 边的权重进行排序
*
* @param cur_edge
* @param size
*/
private void sortEdge(Edge[] cur_edge, int size) {
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
if (edges[i].weight > edges[j].weight) {
Edge tmp = edges[i];
edges[i] = edges[j];
edges[j] = tmp;
}
}
}
}
/**
* 克鲁斯卡尔 核心算法
*/
public Edge[] kruskal() {
edges = getEdges();
int index = 0;
Edge[] curEdges = edges;//存放排序后的边数组
Edge[] rets = new Edge[edgeSize];//用来存放结果
sortEdge(curEdges, edgeSize);//边的权重进行排序
//定义一个数组，用来存放连通分量,用来表示连通关系的
//下标用来表示起点,值表示终点
int[] tempEdge = new int[edgeSize];
for (int i = 0; i < edgeSize; i++) {
int p1 = curEdges[i].start;
int p2 = curEdges[i].end;
int m = getEnd(tempEdge, p1);
int n = getEnd(tempEdge, p2);
//如果m和n没有连接在一起，他们就不相等
//如果相等就有回路
if (m != n) {
rets[index++] = curEdges[i];
if (m > n) {
int temp = n;
n = m;
m = temp;
}
tempEdge[m] = n;
}
}
return rets;
}
/**
* 获取当前节点的最后一个节点，也是当前链中最大值
*
* @param edges
* @param p
* @return
*/
private int getEnd(int[] edges, int p) {
int i = p;
while (edges[i] != 0) {
i = edges[i];
}
return i;
}
class Edge {
int start; //起点
int end; //终点
int weight; //边的权重
public Edge(){}
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
}
Kruskal算法测试及结果
@Test
public void main(){
int[][] m = new int[][]{
{0, 50, 60, I, I, I, I},
{50, 0, I, 65, 40, I, I},
{60, I, 0, 52, I, I, 45},
{I, 65, 52, 0, 50, 30, 42},
{I, 40, I, 50, 0, 70, I},
{I, I, I, 30, 70, 0, I},
{I, I, 45, 42, I, I, 0}
};
init(m);
Edge[] result = kruskal();
int lengh = 0;
for(int i = 0; i < result.length; i++) {
if(null != result[i]){
lengh+= result[i].weight;
}
}
System.out.println("最小生成树的权重之和：" + lengh);
char[] chars = new char[m.length];
chars[0] = 'A';
chars[1] = 'B';
chars[2] = 'C';
chars[3] = 'D';
chars[4] = 'E';
chars[5] = 'F';
chars[6] = 'G';
for (int i = 0; i < result.length; i++) {
if(null != result[i]){
System.out.printf("(%s, %s)---> %d \n",chars[result[i].start], chars[result[i].end], matrix[result[i].start][result[i].end]);
}
}
}
结果：
最小生成树的权重之和：257
(D, F)---> 30
(E, B)---> 40
(D, G)---> 42
(G, C)---> 45
(E, D)---> 50
(A, B)---> 50
1.png
Prim算法
**
* author: bobo
* create time: 2019/1/21 4:26 PM
* email: jqbo84@163.com
*/
public class Prim {
public static final int I = 0xFFF8;
int SIZE = 7;//m为节点的个数
//邻接矩阵
int[][] G = new int[][]{
{0, 28, I, I, I, 10, I},
{28, 0, 16, I, I, I, 14},
{I, 16, 0, 12, I, I, I},
{I, I, 12, 0, 22, I, 18},
{I, I, I, 22, 0, 25, 24},
{10, I, I, I, 25, 0, I},
{I, 14, I, 18, 24, I, 0}
};
//最短路径数组, 对应的前驱索引值
int[] path = new int[SIZE];
//最短权重数组, 存放每次到另个顶点的修改后的权重值，先修改第一行V0
int[] weight;
//最小生成树的权重之和
int minTree;
/**
* 普里姆核心算法
*/
public void prim() {
int k = 0;//表示当前正要处理的顶点Vk
//初始化权重数组
weight = G[0];
//定义一个数组来存放集合U 和集合V 两个集合的顶点的信息
boolean[] flag = new boolean[SIZE];
//先从第一个顶点开始，所以先直接存放在U集合一边
flag[0] = true;
//开始逻辑,求VO到某个顶点的最短路径
for (int v = 1; v < SIZE; v++) {
//在能走的路径中找到最短的一条，也就是在集合V 中找
int min = I;
for (int i = 0; i < SIZE; i++) {
if (!flag[i] && weight[i] < min) {
k = i;//K为U集合到V集合中找到的顶点
min = weight[i];//min找到了最小值的位置
}
}
//如果min = I 表示已经不再有点可以加入最小生成树中
if(min == I){
break;
}
minTree += min;
//找到最短路径后，把它存放在集合U中，然后从这个最短的路径对应的顶点开始找下一轮
flag[k] = true;
//path
path[v] = k;
for (int i = 0; i < SIZE; i++) {
if(!flag[i] && weight[i] > G[k][i]){
weight[i] = G[k][i]; //更新可更新边的权值
}
}
}
}
}
Prim算法测试及结果
@Test
public void main(){
//普里姆算法
prim();
//打印
System.out.print("最短路径：");
for (int i = 0; i < path.length; i++) {
System.out.print(path[i] + " ");
}
System.out.println();
System.out.print("最短权重：");
for (int i = 0; i < weight.length; i++) {
System.out.print(weight[i] + " ");
}
System.out.println();
System.out.println("最小生成树的权重之和 = " + minTree);
}
结果：
最短路径：0 5 4 3 2 1 6
最短权重：0 16 12 22 25 10 14
最小生成树的权重之和 = 99
2.png
