试题查看

首页 > 软件水平考试 > 试题查看
【分析解答题】

[说明]
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选项

你可能感兴趣的试题

某企业准备将3项任务X、Y、Z分配给甲、乙、丙3名程序员,每人分别做一项。估计各设有职工实体Employee(职工号,姓名,性别,年龄,通信地址,家庭成员),其[说明]下面的流程图实现了正整数序列K(1),K(2),…,K(n)的重排,得到[说明]设有一张学生成绩表scores存放在Access数据库Student中,[说明]邻接表是图的一种顺序存储与链式存储结合的存储方法。其思想是:对于图G中的[说明]有若干教师,每个教师只有姓名,一个教师可以指导多名研究生;每名研究生有姓