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

javalearner

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

1. /*  
   
2. *日期:2010-04-18 20:02  
   
3. *开发者:heroyan  
   
4. *联系方式:zndxysf@126.com  
   
5. *功能:无向图最小生成树Kruskal算法实现案例  
   
6. */  
   
7. import java.util.Scanner;   
   
8. import java.util.Arrays;   
   
9. import java.util.ArrayList;   
   
10.   
    
11. public class Kruskal{   
    
12.     private static int MAX = 100;   
    
13.     private ArrayList< Edge> edge = new ArrayList< Edge>();//整个图的边   
    
14.     private ArrayList< Edge> target = new ArrayList< Edge>();//目标边，最小生成树   
    
15.     private int[] parent = new int[MAX];//标志所在的集合   
    
16.     private static double INFINITY = 99999999.99;//定义无穷大   
    
17.     private double mincost = 0.0;//最小成本   
    
18.     private int n;//结点个数   
    
19.       
    
20.     public Kruskal(){}   
    
21.       
    
22.     public static void main(String args[]){   
    
23.         Kruskal sp = new Kruskal();   
    
24.         sp.init();   
    
25.         System.out.println(sp.kruskal());   
    
26.         sp.print();   
    
27.     }   
    
28.     //初始化   
    
29.     public void init(){   
    
30.         Scanner scan = new Scanner(System.in);   
    
31.         int p,q;   
    
32.         double w;   
    
33.            
    
34.         System.out.println("spanning tree begin!Input the node number:");   
    
35.         n = scan.nextInt();   
    
36.         System.out.println("Input the graph(-1,-1,-1 to exit)");   
    
37.            
    
38.         while(true){   
    
39.             p = scan.nextInt();   
    
40.             q = scan.nextInt();   
    
41.             w = scan.nextDouble();   
    
42.             if(p < 0 || q < 0 || w < 0){   
    
43.                 break;   
    
44.             }   
    
45.             Edge e = new Edge();   
    
46.             e.start = p;   
    
47.             e.end = q;   
    
48.             e.cost = w;   
    
49.             edge.add(e);   
    
50.         }   
    
51.            
    
52.         mincost = 0.0;   
    
53.            
    
54.         for(int i = 1; i <= n; ++i){   
    
55.             parent[i] = i;//将每个顶点初始化为一个集合，父节点指向自己。
    
56.         }   
    
57.     }   
    
58.     //集合合并，将父节点为j的改为父节点为k(父节点同为k的合并到一个集合。)
    
59.     public void union(int j, int k){   
    
60.         for(int i = 1; i <= n; ++i){   
    
61.             if(parent[i] == j){   
    
62.                 parent[i] = k;   
    
63.             }   
    
64.         }   
    
65.     }   
    
66.     //prim算法主体   
    
67.     public double kruskal(){   
    
68.         //找剩下的n-2条边   
    
69.         int i = 0;   
    
70.         while(i < n-1 && edge.size() > 0){   
    
71.             //每次取一最小边，并删除   
    
72.             double min = INFINITY;   
    
73.             int tag = 0;   
    
74.             Edge tmp = null;   
    
75.             for(int j = 0; j < edge.size(); ++j){   
    
76.                 Edge tt = edge.get(j);   
    
77.                 if(tt.cost < min){   
    
78.                     min = tt.cost;   
    
79.                     tmp = tt;   
    
80.                 }   
    
81.             }   
    
82.             int jj = parent[tmp.start];   
    
83.             int kk = parent[tmp.end];   
    
84.             //去掉环   
    
85.             if(jj != kk){   
    
86.                 ++i;   
    
87.                 target.add(tmp);   
    
88.                 mincost += tmp.cost;   
    
89.                 union(jj,kk);   
    
90.             }   
    
91.             edge.remove(tmp);   
    
92.         }   
    
93.         if(i != n-1){   
    
94.             System.out.println("no spanning tree");
    
95.              return 0;
    
96.         }   
    
97.       return mincost;
    
98.     }   
    
99.     //打印结果   
    
100.     public void print(){   
     
101.         for(int i = 0; i < target.size(); ++i){   
     
102.             Edge e = target.get(i);   
     
103.             System.out.println("the " + (i+1) + "th edge:" + e.start + "---" + e.end);   
     
104.         }   
     
105.     }   
     
106. }   
     
107.   
     
108. class Edge   
     
109. {   
     
110.     public int start;//始边   
     
111.     public int end;//终边   
     
112.     public double cost;//权重   
     
113. }

复制代码

运行：
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


   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/30/000700343.zip

杀虐

为什么都是你一个人发的呢