【正确答案】 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条边为止。