最小生成树算法

利用prim算法实现的最小生成树算法
将集合U划分为A和B两个子集，不断的将连接A，B集合的最小权值的点不断的从B中加入到A中，直到遍历整个集合U。
算法过程：

先选取一个初始点作为集合A，集合B为ADev补集
选取连接集合A，B的权值最小边，将在集合B中的点添加到集合A中
不断的重复上面的过程
算法复杂度O（n*n）

import java.util.Arrays;

class Graph{
 char[] vexs;
 int[][] edges;
 
 public static final int INF=Integer.MAX_VALUE;
 
 
 public Graph(char[] vexs,int[][] edges) {
  this.edges=edges;
  this.vexs=vexs;
 }
 
 public void prim(int start) {
  if(start<0)
   return;
  int len=vexs.length;
  int[] weights=new int[len];
  char[] prims=new char[len];
  int index=0;
  prims[index++]=vexs[start];
  for(int i=0;i<len;i++)
   weights[i]=edges[start][i];
  
  for(int i=0;i<len;i++){
   if(i==start)
    continue;
   int min=Integer.MAX_VALUE;
   int minINdex = 0;
   for(int j=0;j<len;j++){
    if(weights[j]!=0&&min>weights[j]){
     min=weights[j];
     minINdex=j;
    }
   }
   prims[index++]=vexs[minINdex];
   weights[minINdex]=0;
   for(int j=0;j<len;j++){
    if(weights[j]!=0&&weights[j]>edges[minINdex][j])
     weights[j]=edges[minINdex][j];
   }
  }
  
  int sum=0;
  for(int i=0;i<len-1;i++){
   int iIndexA=getPosition(prims[i]);
   int iIndexB=getPosition(prims[i+1]);
   sum+=edges[iIndexA][iIndexB];
  }
  //System.out.println(sum);
  System.out.println(Arrays.toString(prims));
 }

 private int getPosition(char c) {
  for(int i=0;i<vexs.length;i++)
   if(vexs[i]==c)
    return i;
  return -1;
 }
 
}

public class PrimMethod {

 private static final int INF = Integer.MAX_VALUE;

 public static void main(String[] args) {
   char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
         int edges[][] = {
                  /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
           /*A*/ {   0,  12, INF, INF, INF,  16,  14},
           /*B*/ {  12,   0,  10, INF, INF,   7, INF},
           /*C*/ { INF,  10,   0,   3,   5,   6, INF},
           /*D*/ { INF, INF,   3,   0,   4, INF, INF},
           /*E*/ { INF, INF,   5,   4,   0,   2,   8},
           /*F*/ {  16,   7,   6, INF,   2,   0,   9},
           /*G*/ {  14, INF, INF, INF,   8,   9,   0}};
  Graph graph=new Graph(vexs, edges);
  graph.prim(0);
 }
 
}

kruskal算法
算法描述：先将边的权值进行排序，然后将边权从小到大依次操作，判断即将加入的边是否会在树中生成环，将不能生成环的加入到最小生成树中，否则舍弃这条边。
算法复杂度O（elge）e为边的个数

class Edge{
 int  start;
 int end;
 int value;
 
 public Edge(int start,int end,int value) {
  this.end=end;
  this.start=start;
  this.value=value;
 }
 
}

class Graph1{
 char[] vexs;
 int[][] edges;
 public Graph1(char[] vexs, int[][] edges) {
  super();
  this.vexs = vexs;
  this.edges = edges;
 
 }
 int edgeNum;
 private static final int INF=Integer.MAX_VALUE;
 public void kruskal() {
  //System.out.println(Arrays.toString(vexs));
  for(int i=0;i<vexs.length;i++)
   for(int j=i+1;j<vexs.length;j++)
    if(this.edges[i][j]!=INF)
     edgeNum++;
  
  
  Edge[] edges=buildEdge(this.edges,edgeNum);
  //System.out.println(Arrays.toString(this.edges));
  sortEdge(edges,0,edges.length-1);
  //System.out.println(Arrays.toString(edges));
  Edge[] resEdge=new Edge[edgeNum];
  int index=0;
  int[] edgeRelation=new int[edgeNum];
  for(int i=0;i<edges.length;i++){
   int end1=getEnd(edges[i].start,edgeRelation);
   int end2=getEnd(edges[i].end,edgeRelation);
   if(end1!=end2){
    resEdge[index++]=edges[i];
    edgeRelation[end1]=end2;
   }
  }
  for(int i=0;i<resEdge.length;i++)
   if(resEdge[i]!=null)
   System.out.println(vexs[resEdge[i].start]+"     end="+vexs[resEdge[i].end]);
 }
 
 

 private void sortEdge(Edge[] edges2,int start,int end) {
  if(start>=end)
   return;
  int mid=(end-start)/2;
  sortEdge(edges2, start,start+mid );
  sortEdge(edges2, start+mid+1, end);
  merge(edges2,start,start+mid+1,end);
 }

 private void merge(Edge[] edges2, int start,int mid,int end) {
  int tmp=mid,index=0,s=start;
  Edge[] data=new Edge[end-start+1];
  while(start<mid&&tmp<=end){
   if(edges2[start].value<=edges2[tmp].value){
    data[index++]=edges2[start];
    start++;
   }else{
    data[index++]=edges2[tmp];
    tmp++;
   }
  }
  while(start<mid){
   data[index++]=edges2[start];
   start++;
  }
  while(tmp<=end){
   data[index++]=edges2[tmp];
   tmp++;
  }
  for(int i=0;i<data.length;i++)
   edges2[s+i]=data[i];
 }

 private int getEnd(int end, int[] edgeRelation) {
  while(edgeRelation[end]!=0)
   end=edgeRelation[end];
  return end;
 }

 private Edge[] buildEdge(int[][] edges2, int length) {
  Edge[] edges=new Edge[length];
  int index=0,len=edges2.length;
  for(int i=0;i<len;i++)
   for(int j=i+1;j<len;j++)
    if(edges2[i][j]!=Integer.MAX_VALUE)
     edges[index++]=new Edge(i,j , edges2[i][j]);
  return edges;
 }
}

public class KruskalMethod {

 private static final int INF=Integer.MAX_VALUE;
 
 public static void main(String[] args) {
  char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int edges[][] = {
                 /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
          /*A*/ {   0,  12, INF, INF, INF,  16,  14},
          /*B*/ {  12,   0,  10, INF, INF,   7, INF},
          /*C*/ { INF,  10,   0,   3,   5,   6, INF},
          /*D*/ { INF, INF,   3,   0,   4, INF, INF},
          /*E*/ { INF, INF,   5,   4,   0,   2,   8},
          /*F*/ {  16,   7,   6, INF,   2,   0,   9},
          /*G*/ {  14, INF, INF, INF,   8,   9,   0}};
  Graph1 graph=new Graph1(vexs, edges);
  graph.kruskal();
 }
 
}