Go语言视频零基础入门到精通

五菱

Kruskal算法在实现过程中的关键和难点在于：如何判断欲加入的一条边是否与生成树中已保留的边形成回路？

     我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不相通。当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶点是连通无回路的，若再加入一条边则必然产生回路。


/*  
*日期:2010-04-18 20:02  
*开发者:heroyan  
*联系方式:zndxysf@126.com  
*功能:无向图最小生成树Kruskal算法实现案例  
*/  
import java.util.Scanner;   
import java.util.Arrays;   
import java.util.ArrayList;   
  
public class Kruskal{   
    private static int MAX = 100;   
    private ArrayList< Edge> edge = new ArrayList< Edge>();//整个图的边   
    private ArrayList< Edge> target = new ArrayList< Edge>();//目标边，最小生成树   
    private int[] parent = new int[MAX];//标志所在的集合   
    private static double INFINITY = 99999999.99;//定义无穷大   
    private double mincost = 0.0;//最小成本   
    private int n;//结点个数   
      
    public Kruskal(){}   
      
    public static void main(String args[]){   
        Kruskal sp = new Kruskal();   
        sp.init();   
        System.out.println(sp.kruskal());   
        sp.print();   
    }   
    //初始化   
    public void init(){   
        Scanner scan = new Scanner(System.in);   
        int p,q;   
        double w;   
           
        System.out.println("spanning tree begin!Input the node number:");   
        n = scan.nextInt();   
        System.out.println("Input the graph(-1,-1,-1 to exit)");   
           
        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.cost = w;   
            edge.add(e);   
        }   
           
        mincost = 0.0;   
           
        for(int i = 1; i <= n; ++i){   
            parent = i;//将每个顶点初始化为一个集合，父节点指向自己。
        }   
    }   
    //集合合并，将父节点为j的改为父节点为k(父节点同为k的合并到一个集合。)
    public void union(int j, int k){   
        for(int i = 1; i <= n; ++i){   
            if(parent == j){   
                parent = k;   
            }   
        }   
    }   
    //prim算法主体   
    public double kruskal(){   
        //找剩下的n-2条边   
        int i = 0;   
        while(i < n-1 && edge.size() > 0){   
            //每次取一最小边，并删除   
            double min = INFINITY;   
            int tag = 0;   
            Edge tmp = null;   
            for(int j = 0; j < edge.size(); ++j){   
                Edge tt = edge.get(j);   
                if(tt.cost < min){   
                    min = tt.cost;   
                    tmp = tt;   
                }   
            }   
            int jj = parent[tmp.start];   
            int kk = parent[tmp.end];   
            //去掉环   
            if(jj != kk){   
                ++i;   
                target.add(tmp);   
                mincost += tmp.cost;   
                union(jj,kk);   
            }   
            edge.remove(tmp);   
        }   
        if(i != n-1){   
            System.out.println("no spanning tree");
             return 0;
        }   
      return mincost;
    }   
    //打印结果   
    public void print(){   
        for(int i = 0; i < target.size(); ++i){   
            Edge e = target.get(i);   
            System.out.println("the " + (i+1) + "th edge:" + e.start + "---" + e.end);   
        }   
    }   
}   
  
class Edge   
{   
    public int start;//始边   
    public int end;//终边   
    public double cost;//权重   
}

运行：
C:\work>java Kruskal
spanning tree begin!Input the node number:
5
Input the graph(-1,-1,-1 to exit)
1 2 2
2 5 9
2 3 8
5 4 7
4 1 10
1 3 12
3 4 6
3 5 3
-1 -1 -1
19.0
the 1th edge:1---2
the 2th edge:3---5
the 3th edge:3---4
the 4th edge:2---3