[Prim]Poj 1258 Agri-Net

浏览数：20 / 时间：2015年06月09日

利用Prim算法求最小生成树，其工作原理与Dijkstra相似。

这棵树从一个任意的根节点r开始，一只长大到覆盖V中的所有顶点为止。

算法每一步加入的边都必须是使树的总权重增加量最小的边。

代码转载自：http://www.cnblogs.com/Veegin/archive/2011/04/29/2032388.html

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MaxInt 0x3f3f3f3f
 4 #define N 110
 5 //创建map二维数组储存图表，low数组记录每2个点间最小权值，visited数组标记某点是否已访问
 6 int map[N][N],low[N],visited[N];
 7 int n;
 8  
 9 int prim()
10 {
11     int i,j,pos,min,result=0;
12     memset(visited,0,sizeof(visited));
13     //从某点开始，分别标记和记录该点
14     visited[1]=1;pos=1;
15     //第一次给low数组赋值
16     for(i=1;i<=n;i++)
17         if(i!=pos) 
18             low[i]=map[pos][i];
19     //再运行n-1次
20     for(i=1;i<n;i++){
21     //找出最小权值并记录位置
22          min=MaxInt;
23     for(j=1;j<=n;j++){
24          if(visited[j]==0&&min>low[j]){
25             min=low[j];pos=j;
26         }
27     }
28          
29     //最小权值累加
30     result+=min;
31     //标记该点
32     visited[pos]=1;
33     //更新权值
34     for(j=1;j<=n;j++)
35         if(visited[j]==0&&low[j]>map[pos][j])
36             low[j]=map[pos][j];
37     }
38     return result;
39 }
40  
41 int main()
42 {
43     int i,v,j,ans;
44     while(scanf("%d",&n)!=EOF)
45     {
46     //所有权值初始化为最大
47         memset(map,MaxInt,sizeof(map));
48         for(i=1;i<=n;i++)
49             for(j=1;j<=n;j++)
50             {
51                 scanf("%d",&v);
52                 map[i][j]=map[i][j]=v;
53             }
54             ans=prim();
55             printf("%d\n",ans);
56     }
57     return 0;
58 }