java实现最小生成树的prim算法和kruskal算法

在边赋权图中，权值总和最小的生成树称为最小生成树。构造最小生成树有两种算法，分别是prim算法和kruskal算法。在边赋权图中，如下图所示:

在上述赋权图中，可以看到图的顶点编号和顶点之间邻接边的权值，若要以上图来构建最小生成树。结果应该如下所示:

这样构建的最小生成树的权值总和最小，为17

在构建最小生成树中，一般有两种算法，prim算法和kruskal算法

在prim算法中，通过加入最小邻接边的方法来建立最小生成树算法。首先构造一个零图，在选一个初始顶点加入到新集合中，然后分别在原先的顶点集合中抽取一个顶点，使得构成的边为权值最小，然后将该笔边加入到图中，并将抽出的顶点加入到新集合中，重复这个过程，知道新集合等于原先的集合。

代码如下:

package 最小生成树;  /*   * 最小生成树prim算法，加入最小邻接边生成最小生成树。   * 首先构造一个零图，选择一个初始点加入到集合中，   * 然后分别从原来顶点的集合中抽取一个顶点，   * 选择的标准是构造成的树的权值最小，   * 循序渐进最终生成一棵最小生成树   */  public class prim {   /**    * @author 刘雁冰    * @date 2015-02-13 20:23    */      /*    * m:定义为无法到达的距离    * weight:邻接矩阵表,weight表示权值    * verNum:顶点的个数    * lowerW:到新集合的最小权值    * edge:存储到新集合的边    * checked:判定顶点是否被抽取的集合    */      static int m=Integer.MAX_VALUE;   static int[][] weight={     {0, 0, 0, 0, 0, 0},       {0, m, 6, 9, 5, 13},       {0, 6, m, 6,7,8},       {0, 9,6,m,9,3},       {0, 5,7,9,m,3},       {0,13,8,3,3,m}     };   static int verNum=weight.length;   static int []lowerW=new int[verNum];   static int []edge=new int[verNum];   static boolean []checked=new boolean[verNum];      public void prim(int n,int [][]w){    checked[1]=true;            //抽取第一个顶点        for(int i=1;i<=n;i++){          //初始化顶点集合     lowerW[i]=w[1][i];     edge[i]=1;     checked[i]=false;    }        for(int i=1;i<=n;i++){     int min=Integer.MAX_VALUE;     int j=1;     for(int k=2;k<=n;k++){        //判定是否抽取该顶点      if(lowerW[k]<min&&(!checked[k])){       min=lowerW[k];       j=k;      }     }     if(i<n)                //避免输出第一个顶点到第一个顶点的情况     System.out.println(j+"-->"+edge[j]);          checked[j]=true;           //将顶点加入到新集合中          for(int k=2;k<=n;k++){        //根据新加入的顶点，求得最小的权值      if((w[j][k]<lowerW[k])&&(!checked[k])){       lowerW[k]=weight[j][k];       edge[k]=j;      }     }    }   }      public static void main(String[] args) {    // TODO Auto-generated method stub    prim p=new prim();    p.prim(verNum-1,weight);   }  }

测试结果如下:

在kruskal算法中，根据边的权值以递增的方式逐渐建立最小生成树。具体操作是:将赋权图每个顶点都看做森林，然后将图中每条邻接边的权值按照升序的方式进行排列，接着从排列好的邻接边表中抽取权值最小的边，写入该边的起始顶点和结束顶点，连接顶点将森林构成树，然后读取起始结束顶点的邻接边，优先抽取权值小的邻接边，继续连接顶点将森林构成树。添加邻接边的要求是加入到图中的邻接边不构成回路。如此反复进行，直到已经添加n-1条边为止。

代码如下:

package 最小生成树;  import java.util.ArrayList;  import java.util.Scanner;  /*   * 最小生成树kruskal算法：首先将每个顶点作为一棵森林，升序比较该顶点的邻接边，   * 每次取最小权值的邻接边，将该邻接边连接的顶点与原先顶点构成一棵树，接着寻找   * 下一个顶点，继续按照邻接边权值升序进行比较，取权值最小的构成树...   *    * 该类用一个Edge类构成一个邻接边的信息，包括邻接边的起始顶点与结束顶点，权值。   * 用类Edge创建对象，录入对象信息，按照对象的权值进行比较，符合条件的对象加入   * 到链表中，最终按照链表顺序输出最小生成树。   */  public class kruskal {   /**    * @author 刘雁冰    * @date 2015-02-13 20:23    */      /*    * Max:定义顶点数组的最大值    * edge:链表edge，存储构造的Edge对象    * target:链表trget,存储最终得到结果的Edge对象    * parent:存储顶点信息的数组    * n:顶点数    */   int Max=100;   ArrayList<Edge>edge=new ArrayList<Edge>();   ArrayList<Edge>target=new ArrayList<Edge>();   int[] parent=new int[Max];   Float TheMax=Float.MAX_VALUE;   int n;      public void init(){    /**     * p:起始顶点     * q:结束顶点     * w:边的权值     * n:顶点个数     */    Scanner scan =new Scanner(System.in);    int p,q;    double w;    System.out.println("请输入结点的个数:");    n=scan.nextInt();    System.out.println("按照'A,B,C'的格式输入边与边的信息,ABC分别代表边的起始顶点，结束顶点，权值(输入-1 -1 -1结束输入):");    while(true){     p=scan.nextInt();     q=scan.nextInt();     w=scan.nextDouble();     if(p<0||q<0||w<0)break;     Edge e=new Edge();     e.start=p;     e.end=q;     e.weight=w;     edge.add(e);    }    for(int i=1;i<=n;++i){          //初始化边的信息数组     parent[i]=i;    }   }      /*    * 对象合并，将上一对象的结束边作为下一对象的起始边    */   public void union(int j,int k){    for(int i=1;i<=n;++i){     if(parent[i]==j)      parent[i]=k;    }   }      public void kruskal(){    int i=0;                 //顶点    while(i<n-1&&edge.size()>0){       //如果只有一条边或者没有边跳出     double min=Double.MAX_VALUE;     Edge temp=null;      for(int j=0;j<edge.size();++j){      //遍历图形      Edge tt=edge.get(j);      if(tt.weight<min){           //若两个顶点有权值，即相连      min=tt.weight;           temp=tt;      }    }        //构造一棵树    int jj=parent[temp.start];    int kk=parent[temp.end];            if(jj!=kk){     ++i;                 //以end作为下一条边的start,寻找下一条边     target.add(temp);           //将找到的边放入目标集合中     union(jj,kk);                 }    edge.remove(temp);           //将临时边删除    }    System.out.println("最小生成树的路径是:");    for(int k=0;k<target.size();++k){     //输出最小生成树     Edge e=target.get(k);     System.out.println(e.start+"-->"+e.end);    }   }      public static void main(String[] args) {    // TODO Auto-generated method stub     kruskal kr=new  kruskal();     kr.init();     kr.kruskal();   }  }  /*   * start:起始顶点   * end:结束顶点   * weight:权值   */  class Edge{   public int start;   public int end;   public double weight;  }

调试结果如下: