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

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

admin2019-08-15  123
问题 “破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。
(注意：圈就是回路)
选项
答案 void SpnTree(AdjList g){ ／／用“破圈法”求解带权连通无向图的一棵最小代价生成树 typedef struet{int i，j，w；}node； ／／设顶点信息就是顶点编号，权是整数 node edge[]； scanf(＂％d％d＂，&e，&n)； ／／输入边数和顶点数 for(i=1；i＜=e；i++) ／／输入e条边：顶点，权值 ScaRf(＂％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中w不为0的n—l条边。 提示：此题考查的知识点是最小生成树的定义。连通图的生成树包括图中的全部n个顶点和足以使图连通的n一l条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删，直到剩n一1条边为止。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/0dCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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