一个完整的Prim算法，只是我看不懂，请看的懂的帮我注释一下
这个是书上抄下来的程序，正常运行。
其实注释已经写的很多了，不过我还是看不太懂。
我了解Prim算法的基本原理，大致是明白整个思路的，但是转化成程序后就有点迷糊。
请问：
1.为何两个for循环都是从下标2开始的？尤其是第二个想不通；
2.lowcost数组顾名思义知道是存放最小代价信息的数组，但是具体的说lowcost放着是什么的最小代价，比如“lowcost[i]=c[1][i];”表示的是什么意思（我要带i的语言描述）？
3.closest[i]=1 又是什么含意呢？
4.求教第二个for循环的整层循环是写什么，我要每一行的注释。到底是在作什么？？
----
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 30
#define MAXCOST 1000
/*每一步扫描数组lowcost，在V-U中找出离U最近的顶点，令其为k，并打印边(k,closest[k])*/
/*然后修改lowcost和closest，标记k已经假如U 。c表示图邻接矩阵，弱不存在边(i,j),则c[i][j]的值为一个大于任何权而小于无限打的阐述，这里用MAXCOST表示*/
void prim (int c[MAXVEX][MAXVEX], int n)/*一直图的顶点为{1,2,...,n},c[i][j]为(i,j)的权，打印最小生成树的每条边*/
{
int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX];
for (i=2;i<=n;i++) /*从顶点1开始*/
{
lowcost[i]=c[1][i];
closest[i]=1;
}
closest[1]=0;
for (i=2;i<=n;i++) /*从U之外求离U中某一顶点最近的顶点*/
{
min=MAXCOST;
j=1;
k=i;
while (j<=n)
{
if (lowcost[j]<min && closest[j]!=0)
{
min=lowcost[j];
k=j;
}
j++;
}
printf ("(%d,%d)",closest[k],k); /*打印边*/
closest[k]=0; /* k假如到U中 */
for (j=2;j<=n;j++)
if (closest[j]!=0 && c[k][j]<lowcost[j])
{
lowcost[j]=c[k][j];
closest[j]=k;
}
}
}
void main()
{
int n=7,i,j,mx[MAXVEX][MAXVEX];
for (i=0;i<=n;i++)
for (j=0;j<=n;j++)
mx[i][j]=MAXCOST;
mx[1][2]=50;
mx[1][3]=60;
mx[2][4]=65;
mx[2][5]=40;
mx[3][4]=52;
mx[3][7]=45;
mx[4][5]=50;
mx[5][6]=70;
mx[4][6]=30;
mx[4][7]=42;
printf("最小生成树边集：\n");
prim(mx,n);
}
问题点数：50、回复次数：2Top
1 楼LeeMaRS（小菜虎，仍需努力）回复于 2004-05-02 09:24:45 得分 45
1.为何两个for循环都是从下标2开始的？尤其是第二个想不通；
答：因为Prim算法可以任选起点，通常选定点1为起点，也就是说点1一开始就在U里面了，自然不必出现在第二个循环(在V-U中寻找点)中。
2.lowcost数组顾名思义知道是存放最小代价信息的数组，但是具体的说lowcost放着是什么的最小代价，比如“lowcost[i]=c[1][i];”表示的是什么意思（我要带i的语言描述）？
答：存放的是当前从点集U到点集V-U的最短边长，lowcost[i] = c[1][i]是初始化，开始时点集U中只有点1，因此当前点集U到点集V-U的各最短边长lowcost[i]就等于点1到点i的边权。
3.closest[i]=1 又是什么含意呢？
答：closest[i]记录对应lowcost[i]的边的起点，因为lowcost[i]是当前终点为i的各条边中的最小值，再加上一个closest[i]记录起点，就能确定最小生成树的边了。closest[i] = 1是初始化，自然每一个边都是从点1出发的。
4.求教第二个for循环的整层循环是写什么，我要每一行的注释。到底是在作什么？？
答：
for (i=2;i<=n;i++) /*从U之外求离U中某一顶点最近的顶点*/
{
min=MAXCOST; // 这一段是在U之外找最小值，closest[j] != 0表示是U之外
j=1;
k=i;
while (j<=n)
{
if (lowcost[j]<min && closest[j]!=0)
{
min=lowcost[j];
k=j;
}
j++;
}
printf ("(%d,%d)",closest[k],k); /*打印边，这里就看出closest[k]的用途了嘛*/
closest[k]=0; /* 将点k加入集合U */
for (j=2;j<=n;j++) // 更新最短边和相应起点
if (closest[j]!=0 && c[k][j]<lowcost[j]) //若点j在集合U外(cloest[j] != 0)，而且从U中的点k出发，到达点j的边权小于当前以j为终点的最小权值(c[k][j] < lowcost[j])
{
lowcost[j]=c[k][j]; //更新最小权值
closest[j]=k; //记录新边的起点
}
}
Top
2 楼LeeMaRS（小菜虎，仍需努力）回复于 2004-05-02 09:30:37 得分 5
帖一个我写的Prim的例程，提升一下这个帖子。cc~
Program Example_Prim;
Const
Infinity = MaxLongInt; { 无穷大 }
M = MaxLongInt;
MaxP = 3;
map : Array [1..MaxP, 1..MaxP] Of LongInt =
((M, 10, 40),
(10, M, 20),
(40, 20, M));
Var
{ map : Array [1..100,1..100] Of LongInt;}
{ 邻接矩阵 }
lowcost : Array [1..MaxP] Of LongInt;
{ 记录从已访问过的点集到未访问过的点集中的最短边长 }
closest : Array [1..MaxP] Of LongInt;
{ 记录对应lowcost[p]的边的源点}
edge : Array [1..MaxP-1] Of Record
p1, p2 : LongInt;
End;
{ 记录最小生成树的边, 有N个点, 最小生成树有N-1条边 }
treecost, min, p : LongInt;
{ treecost记录最小生成树的权值, p是记录最小生成树的边数 }
Procedure Prim;
Var
i,j,k : LongInt;
Begin
{ 初始化 }
FillChar(lowcost, SizeOf(lowcost), 0);
FillChar(closest, SizeOf(closest), 0);
treecost:=0; p:=0;
{ 初始化lowcost和closest 从点1开始计算 }
For i:=2 To MaxP Do
Begin
lowcost[i]:=map[1,i]; closest[i]:=1;
End;
For i:=2 To MaxP Do
Begin
{ 选出最小的边 }
min:=lowcost[i]; j:=i;
For k:=2 To MaxP Do
If lowcost[k]<min Then
Begin
min:=lowcost[k]; j:=k;
End;
{ Prim的思想是每次找出一个从已访问点集到未访问点集的边集中最小的一条边, 每次
访问一个点, 把选出的最小边加入最小生成树, 记录权值, 并将这个点加入已访问的
点集中 }
treecost:=treecost+map[j,closest[j]];
lowcost[j]:=Infinity;
Inc(p); edge[p].p1:=closest[j]; edge[p].p2:=j;
{ 重新计算lowcost和closest }
For k:=2 To MaxP Do
If (map[j,k]<lowcost[k]) AND (lowcost[k]<Infinity) Then
Begin
lowcost[k]:=map[j,k]; closest[k]:=j;
End;
End;
End;
Procedure Print;
Var
i : LongInt;
Begin
Writeln('Min cost = ', treecost);
Write('Edges :');
For i:=1 To p Do
Write('(',edge[i].p1,',',edge[i].p2,') ');
Writeln;
End;
Begin
Prim;
Print;
End.Top
