参考答案

正确答案：void SpnTree(AdjList g)／／用“破圈法”求解带权连通无向图的一棵最小代价生成树{typedef struct{int iJw}node；／／设顶点信息就是顶点编号权是整数node edge[]；ScaRf(”％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]；}／／fork=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一1条边。
此问题考查的知识点是最小生成树的定义。连通图的生成树包括图中的全部n个顶点和足以使图连通的n一1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。