免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 3551 | 回复: 10

[算法] C  最小生成树算法一疑问,拜谢回答@-- 已解决:个人眼力问题,打扰! [复制链接]

论坛徽章:
0
发表于 2012-09-19 15:33 |显示全部楼层
本帖最后由 FaintKnowledge 于 2012-09-19 17:06 编辑
  1. 1 void MiniSpanTree_Prim(MGraph G)
  2. 2 {
  3. 3         int min,i,j,k;
  4. 4        int  adjvex[MAXVEX];                
  5. 5        int         lowcost[MAXVEX];               
  6. 6        lowcost[0] =0;                               
  7.                                                        
  8. 7        adjvex[0] = 0 ;                               
  9. 8        for(i = 1; i < G.numVertexes; i++) [color=Red]//循环除下标为0外的全部顶点;[/color]
  10. 9        {
  11. 10                lowost[i] = G.arc[0][i];
  12. 11                adjvex[i] = 0;                  
  13. 12        }
  14. 13        for(i = 1;i < G.numVertexes;i++)     [color=Red]//这两次循环为什么是从等于1开始啊???G.arc[0][0]不需要遍历了吗?[/color]
  15. 14        {  
  16. 15                min = INFINITY;
  17. 16                j=1;k=0;         
  18. 17                while( j < G.numVertexes)       
  19. 18                {
  20. 19                        if(lowcost[j] != 0 && lowcost[j] < min)  
  21. 20                        {
  22. 21                                min =lowcost[j];  
  23. 22                                k = j;                          
  24. 23                        }
  25. 24                        j++;
  26. 25                }
  27. 26                printf("(%d,%d)",adjvex[k],k);
  28. 27                lowcost[k] = 0;               
  29. 28                for(j =1 ;j < numVertexes;j++)         
  30. 29                {
  31. 30                        if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
  32. 31                        {       
  33. 32                                lowcost[j] = G.arc[k][j];       
  34. 33                                adjvex[j] = k;                       
  35.                                                                   
  36. 34                        }
  37. 35                }
  38. 36        }
  39. 37}
复制代码

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2012-09-19 15:35 |显示全部楼层
因为下标0的结点初始化就已经在最小生成树里了, 这么浅显的道理, 大哥.

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2012-09-19 15:43 |显示全部楼层
@FaintKnowledge
linux_c_py_php 发表于 2012-09-19 15:35
因为下标0的结点初始化就已经在最小生成树里了, 这么浅显的道理, 大哥.

论坛徽章:
0
发表于 2012-09-19 15:45 |显示全部楼层
回复 2# linux_c_py_php


1.jpg    
那再追问个问题,比如这个图中:
2.jpg
该选1,还是5啊? 从哪个步骤开始的?

论坛徽章:
0
发表于 2012-09-19 15:46 |显示全部楼层
回复 3# linux_c_py_php


    我了个去了....不用鄙视我两次吧??????/

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2012-09-19 15:50 |显示全部楼层
本帖最后由 linux_c_py_php 于 2012-09-19 15:50 编辑

当然选1, 记住:

循环是不断的将距离最小生成树最近的结点加入到最小生成树, 把握这个概念应该很容易理解吧.

论坛徽章:
0
发表于 2012-09-19 15:52 |显示全部楼层
回复 6# linux_c_py_php

   这俩应该都选...

   

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2012-09-19 16:36 |显示全部楼层
... ... 最后肯定都选, 否则也不叫最小生成树了, 我说的是考虑这两个选择的话选1.

你已经让我无语了.
FaintKnowledge 发表于 2012-09-19 15:52
回复 6# linux_c_py_php

   这俩应该都选...

论坛徽章:
0
发表于 2012-09-19 17:04 |显示全部楼层
本帖最后由 FaintKnowledge 于 2012-09-19 17:06 编辑

回复 8# linux_c_py_php

不好意思,
我刚才只是觉得这个图很抽象,把矩阵列出来也掰不过劲儿来...看的时候没看到这里是i=1,脑子里一直挂着i=0呢...我发誓我看的时候这里是"0"
初始化V0加入最小生成树,这个我能理解,但是V1和V5,这一步纠结来着,如果是这个循环i=0,这真是不容易找到是怎么算的...

我的理解:算法中:8-12行
8        for(i = 1; i < G.numVertexes; i++)       //循环除下标为0外的全部顶点;((((((郁闷...看的时候没看到这里是i=1,脑子里一直挂着i=0呢...我发誓我看的时候是"0"))))))
9        {
10                lowost = G.arc[0];                //将V0顶点与之有边的权值存入数组;这里将保存2个,10,11
11                adjvex = 0;                  
12        }


总之:多谢多谢!!!一点小意思,笑纳 !!!!

1.jpg



论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2012-09-19 17:13 |显示全部楼层
回帖赚RMB...
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP