算法思想

  • 假设G=<V,E>是连通图，TE是G上最小生成树中边的集合。

  • 算法从U={u0}(u0∈V)，TE={ }开始，任取一个顶点u0作为开始点。

  • 重复执行下述操作：在所有u∈U, v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。

注意： 选择最小边时，可能有多条同样权值的边可选，此时任选其一。

Prim

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class Prim{  
    /** 
     * 最小生成树的PRIM算法 
     * @param  graph  图 
     * @param start 开始节点 
     * @param n     图中节点数 
     */  
    public static void PRIM(double [][] graph,int start,int n){  
        /*用于保存集合U到V-U之间的最小边和它的值
        mins[i][0]值表示到该节点i边的起始节点,值为-1表示没有到它的起始点
        mins[i][1]值表示到该边的最小值
        mins[i][1]=0表示该节点已将在集合U中  */
    	double [][] mins=new double [n][2];
    	
    	//初始化mins  
        for(int i=0;i<n;i++){
            if(i==start){  
                mins[i][0]=-1;  
                mins[i][1]=0;  
            }else if( graph[start][i]!=-1){//说明存在（start，i）的边  
                mins[i][0]=start;  
                mins[i][1]= graph[start][i];  
            }else{  
                mins[i][0]=-1;  
                mins[i][1]=Double.MAX_VALUE;  
            }  
        }
        
        for(int i=0;i<n-1;i++){
        	int minV = -1;
            double minW=Double.MAX_VALUE;  
            
            for(int j=0;j<n;j++){ //找到mins中最小值
                if(mins[j][1]!=0&&minW>mins[j][1]){  
                    minW=mins[j][1];  
                    minV=j;  
                }  
            }
            
            mins[minV][1]=0;  
            System.out.println("Prim的第"+i+"条最小边=<"+(int)(mins[minV][0]+1)+","+(minV+1)+">，权重="+minW);  
            
            for(int j=0;j<n;j++){//更新mins数组  
                if(mins[j][1]!=0){  
                    if( graph[minV][j]!=-1&& graph[minV][j]<mins[j][1]){  
                        mins[j][0]=minV;  
                        mins[j][1]= graph[minV][j];  
                    }  
                }  
            }  
        }
        
    } 
    
    public static void main(String [] args){  
        double [][] tree={  
                {-1, 2.0, 4.2, 6.7},  
                {2.0 ,-1,-1, 10.0},  
                {4.2,-1, -1, 4.0},    
                {6.7,10.0,4.0,-1}            
        };  
        Prim.PRIM(tree, 0, 4);  
    }   
}