Ｃ 最小生成树算法一疑问，拜谢回答＠-- 已解决:个人眼力问题,打扰!

FaintKnowledge

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}
    

复制代码

linux_c_py_php

因为下标0的结点初始化就已经在最小生成树里了, 这么浅显的道理, 大哥.

linux_c_py_php

@FaintKnowledge

linux_c_py_php 发表于 2012-09-19 15:35
因为下标0的结点初始化就已经在最小生成树里了, 这么浅显的道理, 大哥.

FaintKnowledge

回复 2# linux_c_py_php


   
那再追问个问题,比如这个图中:

该选1,还是5啊? 从哪个步骤开始的?

FaintKnowledge

回复 3# linux_c_py_php


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

linux_c_py_php

当然选1, 记住:

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

FaintKnowledge

回复 6# linux_c_py_php

   这俩应该都选...

   

linux_c_py_php

... ... 最后肯定都选, 否则也不叫最小生成树了, 我说的是考虑这两个选择的话选1.

你已经让我无语了.

FaintKnowledge 发表于 2012-09-19 15:52
回复 6# linux_c_py_php

   这俩应该都选...

FaintKnowledge

回复 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        }


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

linux_c_py_php

回帖赚RMB...