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

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

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

计算机408

学硕统考专业

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