小生成树并查集最短路

《小生成树并查集最短路》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最小生成树并查集最短路罗方炜lfw2565295@126.com最小生成树问题描述：某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。最小生成树输入：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N(<100)；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号

2、。当N为0时，输入结束，该用例不被处理。输出：对每个测试用例，在1行里输出最小的公路总长度。最小生成树样例输入：312113223441211341412332423450样例输出：35最小生成树最小生成树：在一个具有几个顶点的连通图G中，如果存在子图G‘包含G中所有顶点和一部分边，且不形成回路，则称G’为图G的生成树，代价最小生成树则称为最小生成树。简称MST。最小生成树一般有两种算法：Prim和Kruskal算法今天主要讲Kruskal算法，适用本题，给出的边数，复杂度elong(e)(其中e表示变数)最小生成树算法粗略描述：假设WN

3、=(V,{E})是一个含有n个顶点的连通网，先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。最小生成树做法:定义结点：#defineM10005structnode{intx,y,w;//

4、表示x到y需要花费w}e[M];intn,m,father[M];//n定点数量，m边数量，father[M],每个定点所属集合最小生成树intkruskal(){intres=0,k=1,j=0;for(inti=1;i<=m;i++)father[i]=i;//初始化集合数组while(k

5、,sn2);}j++;}if(k!=n)res=-1;//不可能的情况,产生不了最小生成树returnres;}最小生成树intmain(){while(scanf("%d",&n)&&n){m=n*(n-1)/2;for(inti=0;i

6、1),sn2=findroot(m2);unionset(sn1,sn2);这部分涉及到了集合操作，也就是我们马上要讲的并查集并查集英文：DisjointSet，即“不相交集合”将编号分别为1…N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合。常见两种操作：合并两个集合查找某元素属于哪个集合所以，也称为“并查集”并查集用编号最小的元素标记所在集合；定义一个数组set[1..n]，其中set[i]表示元素i所在的集合；123456789101214261622iSet(i)不相交集合：{1,3,7},{4},{2,5,

7、9,10},{6,8}并查集find1(x){returnset[x];}Merge1(a,b){i=min(a,b);j=max(a,b);for(k=1;k<=N;k++){if(set[k]==j)set[k]=i;}}Θ(1)Θ(N)并查集对于“合并操作”，必须搜索全部元素！树结构如何？并查集每个集合用一棵“有根树”表示定义数组set[1..n]set[i]=i,则i表示本集合，并是集合对应树的根set[i]=j,j<>i,则j是i的父节点.123456789101232134334iSet(i)15247103689并查集find

8、2(x){r=x;while(set[r]!=r)r=set[r];returnr;}merge2(a,b){if(a