问答题
我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。【复旦大学1997六(13分)】
【正确答案】正确答案：连通图的生成树包括图中的全部n个顶点和足以使图连通的n一1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通(一次进入dfs或bfs就能遍历到全部顶点)，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n一1条边为止。
【答案解析】