普里姆算法最小生成树这有一块怎么也看不明白
普里姆算法最小生成树这有一块怎么也看不明白，就是在后面的那个邻接矩阵k行逐个遍历全部顶点我看不太明白，不知道做什么这块，如果不加上是不是也可以呢？// Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G)
{
int min, i, j, k;
int adjvex; // 保存相关顶点下标
int lowcost; // 保存相关顶点间边的权值
lowcost = 0; // V0作为最小生成树的根开始遍历，权值为0
adjvex = 0; // V0第一个加入
// 初始化操作
for( i=1; i < G.numVertexes; i++ )
{
lowcost = G.arc; // 将邻接矩阵第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!=0 && lowcost < min )
{
min = lowcost;
k = j; // 将发现的最小权值的下标存入k，以待使用。
}
j++;
}
// 打印当前顶点边中权值最小的边
printf("(%d,%d)", adjvex, k);
lowcost = 0; // 将当前顶点的权值设置为0，表示此顶点已经完成任务，进行下一个顶点的遍历
// 邻接矩阵k行逐个遍历全部顶点
for( j=1; j < G.numVertexes; j++ )
{
if( lowcost!=0 && G.arc < lowcost )
{
lowcost = G.arc;
adjvex = k;
}
}
}
} 显然你并没有理解prim算法是什么
prim算法是从某个节点开始，不断加边的一个算法。
1. 假设有一棵树只包含一个顶点的v的树T。
2.贪心的选取T和其他顶点之间相连的最小权值的边，并将它加入T中。
3.不断重复1,2知道所有的点相连生成一棵最小生成树。
总的来说这个算法的核心就是这么三步，建议看不懂代码的时候最好能在草稿纸上手动模拟一下
这样对理解算法有很大的帮助，当然过程很煎熬，但还是请忍住
我的好基友曾经写过关于最小生成树的详细方法，同时还佩戴着几道ACM的题，我转到了我的CSDN上，希望能给你帮助
https://blog.csdn.net/u013486414/article/details/39007595
页:
[1]