克鲁斯卡尔算法的核心思想是：在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其构造，直到最后得到一颗最小生成树。 克鲁斯卡尔算法的执行步骤： 第一步：在带权连通图中，将边的权值排序； 第二步：判断是否需要选择这条边（此时图中的边已按权值从小到大排好序）。判断的依据是边的两个顶点是否已连通，如果连通则继续下一条；如果不连通，那么就选择使其连通。 第三步：循环第二步，直到图中所有的顶点都在同一个连通分量中，即得到最小生成树。
下面我用图示法来演示克鲁斯卡尔算法的工作流程，如下图：
首先，将图中所有的边排序（从小到大），我们将以此结果来选择。排序后各边按权值从小到大依次是：
HG < (CI=GF) < (AB=CF) < GI < (CD=HI) < (AH=BC) < DE < BH < DF
接下来，我们先选择HG边，将这两个点加入到已找到点的集合。这样图就变成了，如图
继续，这次选择边CI（当有两条边权值相等时，可随意选一条），此时需做判断。 判断法则：当将边CI加入到已找到边的集合中时，是否会形成回路？ 1.如果没有形成回路，那么直接将其连通。此时，对于边的集合又要做一次判断：这两个点是否在已找到点的集合中出现过？ ①.如果两个点都没有出现过，那么将这两个点都加入已找到点的集合中； ②.如果其中一个点在集合中出现过，那么将另一个没有出现过的点加入到集合中； ③.如果这两个点都出现过，则不用加入到集合中。 2.如果形成回路，不符合要求，直接进行下一次操作。
根据判断法则，不会形成回路，将点C和点I连通，并将点C和点I加入到集合中。如图：
继续，这次选择边GF，根据判断法则，不会形成回路，将点G和点F连通，并将点F加入到集合中。如图：
继续，这次选择边AB，根据判断法则，不会形成回路，将其连通，并将点A和点B加入到集合中。如图：
继续，这次选择边CF，根据判断法则，不会形成回路，将其连通，此时这两个点已经在集合中了，所以不用加入。如图：
继续，这次选择边GI，根据判断法则，会形成回路，如下图，直接进行下一次操作。
继续，这次选择边CD，根据判断法则，不会形成回路，将其连通，并将点D加入到集合中。如图：
继续，这次选择边HI，根据判断法则，会形成回路，直接进行下一次操作。
继续，这次选择边AH，根据判断法则，不会形成回路，将其连通，此时这两个点已经在集合中了，所以不用加入。 继续，这次选择边BC，根据判断法则，会形成回路，直接进行下一次操作。 继续，这次选择边DE，根据判断法则，不会形成回路，将其连通，并将点E加入到集合中。如图：
继续，这次选择边BH，根据法则，会形成回路，进行下一次操作。 最后选择边DF，根据法则，会形成回路，不将其连通，也不用加入到集合中。 好了，所有的边都遍历完成了，所有的顶点都在同一个连通分量中，我们得到了这颗最小生成树。
当数组数据为[1,5,8,7,7,8,0,0,6]时 表示[节点0连着1,1连着5,5连着8,8连着6,2连着8]以及[3连着7,4连着7] 若在加入<5,6时>，通过数组找到相同的顶点的话就说明构成了一个环
package suanfa;
import java.util.Arrays;
public class Main {
static class Graph {
Edge[] edges;
int[][] arr;
}
static class Edge implements Comparable<Edge> {
int begin;
int end;
int weight;
@Override
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}
public static void kruskal(Graph graph) {
//从小到大按权值排好序的edges
Edge[] edges = graph.edges;
int[][] arr = graph.arr;
int[] parent = new int[7];
//顶点的编号为0-6
for(int i =0;i<7;i++){
parent[i] = 0;
}
for(int i=0;i<edges.length;i++){
Edge edge = edges[i];
int rootOfBegin = findParentRoot(edge.begin, parent);
int rootOfend = findParentRoot(edge.end, parent);
if(rootOfBegin!=rootOfend){
System.out.println(String.format("(%d,%d)->%d", rootOfBegin,rootOfend,edge.weight));
parent[rootOfBegin] = rootOfend;
}
}
}
//parent数组用于构造MST判断是否存在环路
/*判断的思想:
1.初始化的时候，数组为[0,0,...,0]
2.第一次循环进来的时候比如(begin=0,end=1,weight=5),由于数组全为0,故返回0和1,
若begin和end的返回值不相等则设置parent[begin]=end,即设置了0的双亲节点是1,即把0节点和1节点加入MST
当数组数据为[1,5,8,7,7,8,0,0,6]时
表示[节点0连着1,1连着5,5连着8,8连着6,2连着8]以及[3连着7,4连着7]
若在加入<5,6时>，通过数组找到相同的顶点的话就说明构成了一个环
3.begin和end的返回值相等，则表示构成了环
*/
private static int findParentRoot(int target,int[] parent){
while(parent[target] > 0){
target = parent[target];
}
return target;
}
public static void main(String[] args) {
//初始化
Graph graph = new Graph();
int[][] arr = new int[7][7];
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
if (i == j)
arr[i][j] = 0;
else {
arr[j][i] = Integer.MAX_VALUE;
}
}
}
arr[0][1] = 7;
arr[0][3] = 5;
arr[1][2] = 8;
arr[1][3] = 9;
arr[1][4] = 7;
arr[2][4] = 5;
arr[3][4] = 15;
arr[3][5] = 6;
arr[4][5] = 8;
arr[4][6] = 9;
arr[5][6] = 11;
for (int i = 0; i < 7; i++) {
for (int j = i; j < 7; j++) {
arr[j][i] = arr[i][j];
}
}
graph.arr = arr;
int k = 0;
Edge[] edges = new Edge[11];
for(int i=0;i<edges.length;i++){
Edge edge = new Edge();
edges[i] = edge;
}
for (int i = 0; i < 6; i++) {
for (int j = i + 1; j < 7; j++) {
if (arr[i][j] < Integer.MAX_VALUE) {
edges[k].begin = i; // 编号较小的结点为首
edges[k].end = j; // 编号较大的结点为尾
edges[k].weight = arr[i][j];
k++;
}
}
}
graph.edges = edges;
Arrays.sort(edges);
//初始化结束
kruskal(graph);
}
}
