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

admin2019-08-15  66

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

选项

答案 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://jikaoti.com/ti/osGjFFFM
0

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