package kruskal;
public class Graph {
 final int max=100;
 /*
  * 顶点节点
  */
 public class VexNode{
  int adjvex;
  int data;
 }
 VexNode[] vexNodes;
 int[] thevexs;
 //顶点集合
 int[][] edges = new int[max][max];
 //边集合
 /*
  * 创建图
  */
 public void createGraph(Graph graph,int[][] A,int[] vexs) {
  thevexs=vexs;
  for (int i = 0; i < vexs.length; i++) {
   for (int j = 0; j < vexs.length; j++) {
    graph.edges[i][j] = A[i][j];
   }
  }
 }
 /*
  * 输出图
  */
 public void printGraph(Graph graph) {
  for (int i = 0; i < graph.thevexs.length; i++) {
   for (int j = 0; j < graph.thevexs.length; j++) {
    //没有路径则输出/
    if (graph.edges[i][j]==-1) {
     System.out.printf("%4s","/");
    } else {
     System.out.printf("%4d",graph.edges[i][j]);
    }
   }
   System.out.println("\n");
  }
 }
}

package kruskal;
public class KruSkal {
 public class Edge{
  int start;
  int end;
  int weight;
 }
 public void SortEdge(Edge[] E,int e) {
  Edge temp;
  int j;
  for (int i = 0; i < e; i++) {
   temp=E[i];
   j=i-1;
   while (j>=0&&temp.weight<E[j].weight) {
    E[j+1] = E[j];
    j--;
   }
   E[j+1] = temp;
  }
 }
 public KruSkal(Graph graph) {
  int i,j,u1,v1,sn1,sn2,k;
  int[] vset = new int[100];
  Edge[] E = new Edge[100];
  k=0;
  for (i=0;i<graph.thevexs.length;i++) {
   for (j=0;j<=i;j++) {
    E[k] = new Edge();
    if (graph.edges[i][j]>0) {
     E[k].start=i;
     E[k].end=j;
     E[k].weight=graph.edges[i][j];
     k++;
    }
   }
  }
  SortEdge(E, k);
  for (i=0;i<graph.thevexs.length;i++) {
   vset[i]=i;
  }
  k=1;
  j=0;
  while (k<graph.thevexs.length) {
   u1=E[j].start;
   v1=E[j].end;
   sn1=vset[u1];
   sn2=vset[v1];
   if (sn1!=sn2) {
    System.out.printf("(%d,%d),权值：%d",u1,v1,E[j].weight);
    System.out.println("\n");
    k++;
    for (i=0;i<graph.thevexs.length;i++) {
     if (vset[i]==sn2) {
      vset[i]=sn1;
     }
    }
   }
   j++;
  }
 }
}

package kruskal;
public class Test {
 public static void main(String[] args) {
  int[] vexs = {0,1,2,3,4};
  int[][] A = {
      {0,1,3,4,7},
      {1,0,2,-1,-1},
      {3,2,0,5,8},
      {4,-1,5,0,6},
      {7,-1,8,6,0}
    };
  Graph graph = new Graph();
  graph.createGraph(graph, A, vexs);
  graph.printGraph(graph);
  KruSkal kruSkal = new KruSkal(graph);
 }
}