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

我要去实习！

普里姆算法最小生成树这有一块怎么也看不明白，就是在后面的那个邻接矩阵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[i] = G.arc[0][i];        // 将邻接矩阵第0行所有权值先加入数组
                adjvex[i] = 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;       
                        }
                }
        }
}

最佳答案

月排行榜 / 总排行榜

Rocky0429

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

跳转到最佳答案楼层

Rocky0429

显然你并没有理解prim算法是什么

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

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

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

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