Chinaunix首页 | 论坛 | 博客
  • 博客访问: 422734
  • 博文数量: 71
  • 博客积分: 1525
  • 博客等级: 上尉
  • 技术积分: 605
  • 用 户 组: 普通用户
  • 注册时间: 2011-08-05 17:28
文章分类

全部博文(71)

文章存档

2012年(21)

2011年(50)

分类: C/C++

2012-03-06 20:32:52

自己根据kruakal的算法(核心是贪心算法)描述写了一个最小生成树的代码,
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <strings.h>

  4. #define INT32 int
  5. #define MAXNUMEDGE 1024
  6. #define PRINTF

  7. typedef struct EDGE_H
  8. {
  9.     INT32 u;
  10.     INT32 v;
  11.     INT32 key;
  12. }EDGE;

  13. //边从0开始计数
  14. EDGE edge[MAXNUMEDGE]; //用来存储所有的边的数据
  15. static INT32 numberofedge;
  16. EDGE *minspanedge; //生成树时用到的边
  17. INT32 *minspancity; //使用的边所属于的集合

  18. //交换边
  19. int swapedge(INT32 iedge, INT32 jedge)
  20. {
  21.     if(iedge>= numberofedge||jedge>=numberofedge)
  22.         return 0;

  23.     EDGE tmp;
  24.     tmp.u = edge[iedge].u;
  25.     tmp.v = edge[iedge].v;
  26.     tmp.key = edge[iedge].key;

  27.     edge[iedge].u = edge[jedge].u;
  28.     edge[iedge].v = edge[jedge].v;
  29.     edge[iedge].key = edge[jedge].key;

  30.     edge[jedge].u = tmp.u;
  31.     edge[jedge].v = tmp.v;
  32.     edge[jedge].key = tmp.key;

  33.     return 1;

  34. }

  35. /*
  36.  * 得到两个边的较小边
  37.  * */
  38. INT32 minedge(const int iedge,const int jedge)
  39. {
  40.     int minnumedge;
  41.     minnumedge = edge[iedge].key>edge[jedge].key?jedge:iedge;
  42.     return minnumedge;
  43. }

  44. /*
  45.  * 通过最小堆的方式来每次得到最小边
  46.  * */
  47. void minheapofedge(INT32 count)
  48. {
  49.    int i;
  50.    INT32 minkeynum;
  51.    for(i=((numberofedge-count)>>1)-1; i>=0; i--)
  52.    {
  53.        if(((i>>1) 2)<(numberofedge-count))//右结点存在
  54.        {
  55.            minkeynum = minedge((i>>1) 2,(i>>1) 1);
  56.            
  57.            if(edge[i].key>edge[minkeynum].key)//做交换
  58.            {
  59.                swapedge(i,minkeynum);
  60.            }
  61.        }
  62.        else//右节点不存在
  63.        {
  64.            if(edge[i].key>edge[(i>>1) 1].key)
  65.            {
  66.                swapedge(i,(i>>1) 1);
  67.            }
  68.        }
  69.    }
  70. }

  71. /*
  72.  * 查找元素是否属于集合,返回集合的头
  73.  * */
  74. INT32 isset(const INT32 ucity)
  75. {
  76.     INT32 tempcity=ucity;
  77.     if(ucity == minspancity[ucity]){}
  78.     else
  79.     {
  80.         while(tempcity != minspancity[tempcity])
  81.         {
  82.             tempcity = minspancity[tempcity];
  83.         }
  84.     }
  85.     printf("isset:ucity:%d,set:%d\n",ucity,tempcity);
  86.     return tempcity;
  87. }

  88. /*
  89.  * 合并两个集合
  90.  * */
  91. void mergeset(INT32 uset,INT32 vset)
  92. {
  93.     if(minspancity[uset]>minspancity[vset])
  94.         minspancity[uset]=minspancity[vset];
  95.     else
  96.         minspancity[vset]=minspancity[uset];
  97. }
  1. /*
  2.  * 最小生成树
  3.  * */
  4. void minspantree()
  5. {
  6.     
  7.     INT32 i,count=0;
  8.     INT32 ucity,vcity;
  9.     EDGE minedge;
  10.     for(i=0; i<numberofedge; i )
  11.     {
  12.        minheapofedge(count);
  13.        minedge = edge[0];//得到了最小边 //------------------------------------------(1)
  14. #ifdef PRINTF
  15. printf("minedge:u%d,v%d,key%d\n",minedge.u,minedge.v,minedge.key);
  16. #endif
  17.        ucity = isset(minedge.u);
  18.        vcity = isset(minedge.v);
  19.        if(ucity!=vcity)
  20.        {
  21.            //把两个集合合并
  22.            mergeset(ucity,vcity);

  23.            //把边添加进最小生成树里面
  24.            minspanedge[count] = minedge;
  25.            count ;

  26.        }
  27.        else
  28.        {
  29.            /*
  30.             if(minspancity[ucity]>minspancity[vcity])
  31.                 minspancity[vcity] = minspancity[ucity];
  32.             else
  33.                 minspancity[ucity] = minspancity[vcity];
  34.                 */
  35.        }

  36.        //把选出的边处理了
  37.        swapedge(0,numberofedge-i-1);
  38.        
  39.     }
  40. }


  41. /*
  42.  * 读取道路的数据
  43.  * */
  44. int readroad()
  45. {
  46.     int ucity,vcity,distance;
  47.     int i;
  48.     for(i=0; i<numberofedge; i )
  49.     {
  50.         scanf("%d %d %d",&ucity,&vcity,&distance);
  51.         edge[i].u = ucity;
  52.         edge[i].v = vcity;
  53.         edge[i].key = distance;
  54.     }
  55.     return i;

  56. }


  57. int main()
  58. {
  59.     printf("请输入城市个数和城市之间的道路条数\n");
  60.     printf("请输入具体的两个城市和道路名\n");

  61.     int numofcities,cities,i;
  62.     scanf("%d %d",&numofcities,&cities);
  63.     numberofedge = cities;
  64.     minspanedge = (EDGE *)malloc(sizeof(EDGE)*numberofedge);
  65.     bzero(minspanedge,sizeof(minspanedge));
  66.     minspancity = (INT32 *)malloc(sizeof(INT32)*numofcities);

  67.     for(i=0; i<numofcities; i )
  68.         minspancity[i] = i;

  69.     if(numberofedge != readroad()||numberofedge<numofcities-1)
  70.     {
  71.         printf("readroad read error!\n");
  72.         return ;
  73.     }
  74.   /*
  75.     swapedge(0,1);
  76.     for(i=0; i<numberofedge; i )
  77.     {
  78.     printf("%d %d %d\n",edge[i].u,edge[i].v,edge[i].key);
  79.     }
  80. */
  81.     minspantree();

  82.     printf("城市 城市 距离\n");
  83.     for(i=0; i<numofcities-1; i )
  84.         printf("%d %d %d\n",minspanedge[i].u,minspanedge[i].v,minspanedge[i].key);
  85.     


  86. }

在这次写的代码中发现思路上都是正确的,每个函数的代码都是正确的,但是在变量的使用上太不小心了,就是因为变量的错误导致运行的结果出现错误。

结构体是可以直接赋值的,如(1)处。
阅读(2094) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~