问题:--------------------------------------
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=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]=c[k][j]; //更新最小权值 closest[j]=k; //记录新边的起点 } } }
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。