public class Kruskal {
public static void main(String[] args) {
//二维数组 分别存储边的起点 终点 和权值
int [][]edges = {{0,1,6},{0,2,1},{0,3,5},{1,2,5},{1,4,3},{2,3,5},{2,4,6},{2,5,4},{3,5,2},{4,5,6}};
int []connect = {0,1,2,3,4,5};//辅助数组 用来存储两个顶点是否连通 初始都不连通
quick_sort(edges,0,edges.length-1);//对边进行排序
for(int i=0;i<edges.length;i++){
int v1 = edges[i][0]; //边的起点
int v2 = edges[i][1]; //边的终点
int vc1 = connect[v1]; //起点的连通状态
int vc2 = connect[v2]; //终点的连通状态
if(vc1 != vc2){ //如果两个点不连通 则将其加入到最小生成树 并将连通状态改为相同的状态
System.out.println((v1+1)+"->"+(v2+1));
for(int j=0;j<connect.length;j++){
if(connect[j] == vc2)
connect[j] = vc1;
}
}
}
}
public static void quick_sort(int a[][],int low,int high){
if(low < high){
int k = sort(a,low,high);
quick_sort(a,low,k-1);
quick_sort(a,k+1,high);
}
}
public static int sort(int a[][],int low,int high){
int[] k = a[low];
while(low<high){
while(low <high && k[2] <= a[high][2])
high--;
a[low] = a[high];
while(low <high && k[2] >= a[low][2])
low++;
a[high] = a[low];
}
a[low] = k;
return low;
}
}