【分析解答题】
[说明]
kruskAl算法是一种构造图的最小生成树的方法。设g为一无向连通图,令t是由g的顶点构成的于图,kmskAl算法的基本思想是为t添加适当的边使之成为最小生成树:初始时,t中的点互相不连通;考察g的边集E中的每条边,若它的两个顶点在t中不连通,则将此边添加到t中,同时合并其两顶点所在的连通分量,如此下去,当添加了n-1条边时,t的连通分量个数为1,t便是g的一棵最小生成树。
下面的函数voiD kruskAlEDgEtypE EDgEs[],int n)利用kruskAl算法,构造了有n个顶点的图 EDgEs的最小生成树。其中数组FAthEr[]用于记录t中顶点的连通性质:其初值为FAthEr[i]=-1 (i=0,1,…,n-1),表示各个顶点在不同的连通分量上;若有FAthEr[i]=j,j>-1,则顶点i,j连通;函数int FinD(int FAthEr[],int v)用于返回顶点v所在树形连通分支的根结点。
[函数]
#DEFinE mAxEDgE、1000
typEDEF struCt
int v1;
int v2;
EDgEtypE;
voiD kruskAlEDgEtypE EDgEs[],int n)
int FAthEr[mAxEDgE];
int i,j,vF1,vt2;
For(i=0;i<n;i+ +) FAthEr[i]=-1;
i=0;
j=0;
whilE(i<mAxEDgE、&& j< (1) )
vF1=FinD(FAthEr,EDgEs[i].v1);
vF2=FinD(FAthEr,EDgEs[i].v2);
iF( (2) )
(3) =vF1;
(4) ;
printF("%3D%3D\n",EDgEs[i].v1,EDgEs[i].v2);
(5) ;
int FinD(int FAthEr[],int v)
int t;
t=v;
whilE(FAthEr[t]>=0) t=FAthEr[t];
rEturn(t);
查看答案解析
参考答案:
正在加载...
答案解析
正在加载...
根据网考网移动考试中心的统计,该试题:
0%的考友选择了A选项
0%的考友选择了B选项
0%的考友选择了C选项
0%的考友选择了D选项