2011年江西省 2011江西省数据要领基础.doc

2011年江西省 2011江西省数据要领基础 1、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) //用“破圈法”求解带权连通无向图的一棵最小代价生成树。 {typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数 node edge[]; scanf( quot;%d%dquot;,amp;e,amp;n) ; //输入边数和顶点数。 for (i=1;ilt;=e;i++) //输入e条边：顶点，权值。 scanf(quot;%d%d%dquot; ,amp;edge[i].i ,amp;edge[i].j ,amp;edge[i].w); for (i=2;ilt;=e;i++) //按边上的权值大小，对边进行逆序排序。 {edge[0]=edge[i]; j=i-1; while (edge[j].wlt;edge[0].w) edge[j+1]=edge[j--]; edge[j+1]=edge[0]; }//for