广西2015年理论学习
【一】:2015年广西壮族自治区理论数据加强
1、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。
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].wedge[0].w)  ...