Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1661636
  • 博文数量: 695
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 4027
  • 用 户 组: 普通用户
  • 注册时间: 2013-11-20 21:22
文章分类

全部博文(695)

文章存档

2018年(18)

2017年(74)

2016年(170)

2015年(102)

2014年(276)

2013年(55)

分类: C/C++

2014-07-02 12:50:38


今天从志权师兄那里学会了最小生成树。所谓生成树,就是n个点之间连成n-1条边的图形。而最小生成树,就是权值(两点间直线的值)之和的最小值。

  

         首先,要用二维数组记录点和权值。如上图所示无向图:

int map[7][7];
       map[1][2]=map[2][1]=4;
       map[1][3]=map[3][1]=2;
       ......

      然后再求最小生成树。具体方法是:

1.先选取一个点作起始点,然后选择它邻近的权值最小的点(如果有多个与其相连的相同最小权值的点,随便选取一个)。如1作为起点。

visited[1]=1;

pos=1;

//用low[]数组不断刷新最小权值,low[i](0

low[1]=0;  //起始点i到邻近点的最小距离为0

low[2]=map[pos][2]=4;

low[3]=map[pos][3]=2;

low[4]==map[pos][4]=3;

low[5]=map[pos][5]=MaxInt;  //无法直达

low[6]=map[pos][6]=MaxInt;

 

  2.再在伸延的点找与它邻近的两者权值最小的点。

//low[]以3作当前位置进行更新

visited[3]=1;

pos=3;

low[1]=0;   //已标记,不更新

low[2]=map[1][2]=4;  //比5小,不更新

low[3]=2;  //已标记,不更新

low[4]=map[1][4]=3;   //比1大,更新后为:low[4]=map[3][4]=1;

low[5]=map[1][5]=MaxInt;//无法直达,不更新

low[6]=map[1][6]=MaxInt;//比2大,更新后为:low[6]=map[3][6]=2;

 

    3.如此类推...

当所有点都连同后,结果最生成树如上图所示。

     所有权值相加就是最小生成树,其值为2+1+2+4+3=12。

     至于具体代码如何实现,现在结合POJ1258例题解释。代码如下:


点击(此处)折叠或打开

  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) low[i]=map[pos][i];
  18. //再运行n-1次
  19.     for(i=1;i<n;i++)
  20.     {
  21. //找出最小权值并记录位置
  22.      min=MaxInt;
  23.      for(j=1;j<=n;j++)
  24.          if(visited[j]==0&&min>low[j])
  25.          {
  26.              min=low[j];pos=j;
  27.          }
  28. //最小权值累加
  29.     result+=min;
  30. //标记该点
  31.     visited[pos]=1;
  32. //更新权值
  33.     for(j=1;j<=n;j++)
  34.         if(visited[j]==0&&low[j]>map[pos][j])
  35.             low[j]=map[pos][j];
  36.     }
  37.     return result;
  38. }
  39.  
  40. int main()
  41. {
  42.     int i,v,j,ans;
  43.     while(scanf("%d",&n)!=EOF)
  44.     {
  45. //所有权值初始化为最大
  46.         memset(map,MaxInt,sizeof(map));
  47.         for(i=1;i<=n;i++)
  48.             for(j=1;j<=n;j++)
  49.             {
  50.                 scanf("%d",&v);
  51.                 map[i][j]=map[i][j]=v;
  52.             }
  53.             ans=prim();
  54.             printf("%d\n",ans);
  55.     }
  56.     return 0;
  57. }
http://www.cnblogs.com/Veegin/archive/2011/04/29/2032388.html

阅读(1016) | 评论(0) | 转发(0) |
0

上一篇:快速排序

下一篇:正则在C语言中的应用

给主人留下些什么吧!~~