最小生成树的prime算法

柔情只为你懂 2022-07-16 11:15 107阅读 0赞

1.  /\*\* 
2.   \* 最小生成树的prim[算法][Link 1] 
3.   \* @author liuy 
4.   \*/  
5.  **public** **class** Prim \{  
6.        
7.      **public** **static** **void** prim(**int** num, **float**\[\]\[\] weight) \{  //num为顶点数，weight为权  
8.          **float**\[\] lowcost = **new** **float**\[num + 1\];  //到新集合的最小权  
9.            
10.         **int**\[\] closest = **new** **int**\[num + 1\];  //代表与s集合相连的最小权边的点  
11.           
12.         **boolean**\[\] s = **new** **boolean**\[num + 1\];  //s\[i\] == true代表i点在s集合中  
13.           
14.         s\[1\] = **true**;  //将第一个点放入s集合  
15.           
16.         **for**(**int** i = 2; i <= num; i++) \{  //初始化辅助数组  
17.             lowcost\[i\] = weight\[1\]\[i\];  
18.             closest\[i\] = 1;  
19.             s\[i\] = **false**;  
20.         \}  
21.           
22.         **for**(**int** i = 1; i < num; i++) \{  
23.             **float** min = Float.MAX\_VALUE;  
24.             **int** j = 1;  
25.             **for**(**int** k = 2; k <= num; k++) \{  
26.                 **if**((lowcost\[k\] < min) && (!s\[k\])) \{ //根据最小权加入新点  
27.                     min = lowcost\[k\];  
28.                     j = k;  
29.                 \}  
30.             \}  
31.               
32.             System.out.println("加入点" + j + ". " + j + "---" + closest\[j\]);//新加入点的j和与j相连的点  
33.               
34.             s\[j\] = **true**;//加入新点j  
35.               
36.             **for**(**int** k = 2; k <= num; k++) \{  
37.                 **if**((weight\[j\]\[k\] < lowcost\[k\]) && !s\[k\]) \{ //根据新加入的点j,求得最小权  
38.                     lowcost\[k\] = weight\[j\]\[k\];  
39.                     closest\[k\] = j;  
40.                 \}  
41.             \}  
42.         \}  
43.     \}  
44.       
45.     **public** **static** **void** main(String\[\] args) \{  
46.         //              ①  
47.         //            /  |  /  
48.         //           6   1   5  
49.         //          /    |    /  
50.         //        ②-5--③--5--④  
51.         //         /    //    /  
52.         //          3  6  4  2  
53.         //           //    //  
54.         //           ⑤--6-⑥  
55.         //最小生成树为：  
56.         //              ①  
57.         //               |     
58.         //               1      
59.         //               |       
60.         //        ②-5--③        ④  
61.         //         /     /    /  
62.         //          3     4  2  
63.         //           /     //  
64.         //           ⑤      ⑥  
65.         //  
66.         **float** m = Float.MAX\_VALUE;  
67.         **float**\[\]\[\] weight = \{ \{ 0, 0, 0, 0, 0, 0, 0\},  
68.                             \{ 0, m, 6, 1, 5, m, m\},  
69.                             \{ 0, 6, m, 5, m, 3, m\},  
70.                             \{ 0, 1, 5, m, 5, 6, 4\},  
71.                             \{ 0, 5, m, 5, m, m, 2\},  
72.                             \{ 0, m, 3, 6, m, m, 6\},  
73.                             \{ 0, m, m, 4, 2, 6, m\}\};//上图的矩阵  
74.         prim(weight.length - 1, weight);  
75.         //加入点3. 3---1  
76.         //加入点6. 6---3  
77.         //加入点4. 4---6  
78.         //加入点2. 2---3  
79.         //加入点5. 5---2  
80.     \}  
81. \}

[Link 1]: http://lib.csdn.net/base/datastructure