2. 考研
  3. “破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)

“破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)

admin2019-08-01  34
问题 “破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)
选项
答案void SpnTree(AdjList g){ ／／用“破圈法”求解带权连通无向图的一棵最小代价生成树 tvpedef struct|int i，j，w；}node； ／／设顶点信息就是顶点编号，权是整数 node edge[]； scanf("％d％d"，&e，&n)； ／／输入边数和顶点数 for(i=1：i＜=e；i++) ／／输入e条边：顶点，权值 scanf("％d％d％d"，&edge[i]．i，&edge[i]．j，&edge[i].W)； for(i=2；i＜=e；i++){ ／／按边上的权值大小，对边进行逆序排序 edge[0]=edge[i]；j=i一1； while(edge[j]．w＜edge[0]．w)edge[j+1]=edge[j--]； edge[j+1]=edge[0]； }／／for k=1：eg=e； while(eg＞=n){ ／／破圈，直到边数e=n一1 if(connect(k)) ／／删除第k条边若仍连通 {edge[k]．W=0；eg一一；} ／／测试下一条边edge[k]，权值置0表示该边被删除 k++； ／／下条边 }／／while } connect()是测试图是否连通的函数，可用DFS函数或BFS函数实现，若是连通图，一次进入DFS函数或BFS函数就可遍历完全部顶点,否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。“破圈”结束后，可输出edge中ω不为0的n—1条边。
解析
转载请注明原文地址:https://kaotiyun.com/show/4NCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)