鱼C论坛

 找回密码
 立即注册
查看: 2464|回复: 1

[已解决]普里姆算法最小生成树这有一块怎么也看不明白

[复制链接]
发表于 2018-4-2 20:58:04 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
普里姆算法最小生成树这有一块怎么也看不明白,就是在后面的那个邻接矩阵k行逐个遍历全部顶点我看不太明白,不知道做什么这块,如果不加上是不是也可以呢?
// Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G)
{
        int min, i, j, k;
        int adjvex[MAXVEX];                // 保存相关顶点下标
        int lowcost[MAXVEX];        // 保存相关顶点间边的权值
       
        lowcost[0] = 0;                        // V0作为最小生成树的根开始遍历,权值为0
        adjvex[0] = 0;                        // V0第一个加入
       
        // 初始化操作
        for( i=1; i < G.numVertexes; i++ )
        {
                lowcost = G.arc[0];        // 将邻接矩阵第0行所有权值先加入数组
                adjvex = 0;                                // 初始化全部先为V0的下标
        }
       
        // 真正构造最小生成树的过程
        for( i=1; i < G.numVertexes; i++ )
        {
                min = INFINITY;                // 初始化最小权值为65535等不可能数值
                j = 1;
                k = 0;
               
                // 遍历全部顶点
                while( j < G.numVertexes )
                {
                        // 找出lowcost数组已存储的最小权值
                        if( lowcost[j]!=0 && lowcost[j] < min )
                        {
                                min = lowcost[j];
                                k = j;                // 将发现的最小权值的下标存入k,以待使用。
                        }
                        j++;
                }
               
                // 打印当前顶点边中权值最小的边
                printf("(%d,%d)", adjvex[k], k);
                lowcost[k] = 0;                // 将当前顶点的权值设置为0,表示此顶点已经完成任务,进行下一个顶点的遍历
               
                // 邻接矩阵k行逐个遍历全部顶点
                for( j=1; j < G.numVertexes; j++ )
                {
                        if( lowcost[j]!=0 && G.arc[k][j] < lowcost[j] )
                        {
                                lowcost[j] = G.arc[k][j];
                                adjvex[j] = k;       
                        }
                }
        }
}
最佳答案
2018-4-5 22:33:14
显然你并没有理解prim算法是什么

prim算法是从某个节点开始,不断加边的一个算法。

1. 假设有一棵树只包含一个顶点的v的树T。
2.贪心的选取T和其他顶点之间相连的最小权值的边,并将它加入T中。
3.不断重复1,2  知道所有的点相连生成一棵最小生成树。

总的来说这个算法的核心就是这么三步,建议看不懂代码的时候最好能在草稿纸上手动模拟一下
这样对理解算法有很大的帮助,当然过程很煎熬,但还是请忍住

我的好基友曾经写过关于最小生成树的详细方法,同时还佩戴着几道ACM的题,我转到了我的CSDN上,希望能给你帮助
https://blog.csdn.net/u013486414/article/details/39007595


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-4-5 22:33:14 | 显示全部楼层    本楼为最佳答案   
显然你并没有理解prim算法是什么

prim算法是从某个节点开始,不断加边的一个算法。

1. 假设有一棵树只包含一个顶点的v的树T。
2.贪心的选取T和其他顶点之间相连的最小权值的边,并将它加入T中。
3.不断重复1,2  知道所有的点相连生成一棵最小生成树。

总的来说这个算法的核心就是这么三步,建议看不懂代码的时候最好能在草稿纸上手动模拟一下
这样对理解算法有很大的帮助,当然过程很煎熬,但还是请忍住

我的好基友曾经写过关于最小生成树的详细方法,同时还佩戴着几道ACM的题,我转到了我的CSDN上,希望能给你帮助
https://blog.csdn.net/u013486414/article/details/39007595


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 23:22

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表