1、数据结构Data Structure第十第十三三章章 最小生成树最小生成树第第13章章 最小生成树最小生成树n生成树与最小生成树生成树与最小生成树nKruskal算法算法nPrim算法算法n算法的正确性算法的正确性生成树生成树n生成树是无向连通图的极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添加一条边之后，必定会形成回路或环。ABCDEHMABCDEHM无向图G 无向图G的生成树 最小生成树最小生成树(Minimum spanning tree,MST)n定义定义：加权无向图的所有生成树中边的权值（代价）之和最小的树。1243566165556342124356
2、15342最小代价生成树Application:Network designApplicationsnMST is fundamental problem with diverse applications.nDithering.nCluster analysis.nMax bottleneck paths.nReal-time face verification.nLDPC codes for error correction.nImage registration with Renyi entropy.nFind road networks in satellite and aerial
3、imagery.nReducing data storage in sequencing amino acids in a protein.nModel locality of particle interactions in turbulent fluid flows.nAutoconfig protocol for Ethernet bridging to avoid cycles in a network.nApproximation algorithms for NP-hard problems(e.g.,TSP,Steiner tree).nNetwork design(commun
4、ication,electrical,hydraulic,computer,road).http:/www.ics.uci.edu/eppstein/gina/mst.html第第13章章 最小生成树最小生成树n生成树与最小生成树生成树与最小生成树nKruskal算法算法nPrim算法算法n算法的正确性算法的正确性Kruscal 算法算法n基本思想：考虑图中权值最小的边。如果加入这条边不会导致回路，则加入；否则考虑下一条边，直到包含了所有的顶点n实现：n初始时，设置生成树为（V，），如果V有n个顶点，则初始的生成树为具有n个连通分量的树。n按权值的大小逐个考虑所有的边，如果该边的加入能连接两个
5、连通分量，则加入。当生成树只有一个连通分量时，算法结束。12435661655563421、初始连通分量：1,2,3,4,5,62、反复执行添加、放弃动作。边 动作 连通分量 (1,3)添加1,3,4,5,6,2 (4,6)添加1,3,4,6,2,5 (2,5)添加1,3,4,6,2,5 (3,6)添加1,3,4,6,2,5 (1,4)放弃因构成回路 (3,4)放弃因构成回路 (2,3)添加1,3,4,5,6,2最小代价生成树12435615342算法难点及解决方案算法难点及解决方案n如何从所有边中选择代价最小的边：n用一个优先级队列来实现。将所有的边放入一个优先级队列，边的优先级就是它的权值
6、权值越小，优先级越高。n如何判断加入一条边后会不会形成回路：n用并查集来实现。将一个连通分量表示为并查集中的一个子集，检查一条边加入后会不会形成回路可以通过对边的两个端点分别执行Find操作。如果两个Find的结果相同，则表示两个端点已连通，加入这条边会形成回路，否则将这条边加入生成树。添加边的操作就是一个Union操作，将两个端点所属的子集归并起来，表示其中的所有顶点都已连通。定义优先级队列中的元素类型定义优先级队列中的元素类型struct edge int beg,end;/边的起点、终点和权值TypeOfEdge w;bool operator(const edge&rp)constr
7、eturn w rp.w;/重载小于运算符;kruskal算法的算法的实现template void adjListGraph:kruskal()const int edgesAccepted=0，u,v;edgeNode*p;edge e;DisjointSet ds(Vers);/定义一个并查集 priorityQueue pq;/定义一个关于边的优先级队列 /将所有的边放入优先级队列 for(int i=0;inext)if(i end)/每条边只入队一次 e.beg=i;e.end=p-end;e.w=p-weight;pq.enQueue(e);/开始归并 while(edgesAc
8、cepted Vers-1)/选择边数不满n-1时 e=pq.deQueue();/取出权值最小的边 u=ds.Find(e.beg);v=ds.Find(e.end);if(u!=v)/边的起点和终点在不同的连通子图 edgesAccepted+;ds.Union(u,v);/加入(u,v)归并两个连通子图 cout (verListe.beg.ver ,verListe.end.ver )t;时间复杂度时间复杂度n生成优先级队列的for循环将所有的边入队。需要执行|E|次入队，建堆时间为log|E|,生成优先级队列所需时间是O(|E|log|E|)。n在最坏的情况下，归并的循环可能需要检查
9、所有的边。对于每条边，最多需要执行两次Find操作和一次Union操作。因此，归并循环的最坏情况的时间复杂度是O(|E|log|V|)。n在一个连通图中，一般边数总比结点数大，所以，Kruskal算法的时间复杂度是O(E|log|E|)。第第13章章 最小生成树最小生成树n生成树与最小生成树生成树与最小生成树nKruskal算法算法nPrim算法算法n算法的正确性算法的正确性Prim算法算法n从顶点的角度出发。初始时，顶点集U为空，然后逐个加入顶点，直到包含所有顶点。n过程：首先选择一个顶点，加入顶点集。然后重复下列工作，直到U=Vn选择连接U 和V-U 中代价最小的边（u，v）n把（u，v）
10、加入生成树的边集，v加入到Uv1v2v6v7v3v4v524213107584612,4,5,61,3(1,3)(1,2,6),(1,3,1),(1,4,5)22,4,51,3,6(3,6)(3,2,5),(3,4,5),(3,5,6),(3,6,4)32,51,3,4,6(6,4)(3,2,5),(6,4,2),(6,5,6)451,2,3,4,6(3,2)(3,2,5),(6,5,6),52,3,4,5,61初始时1V-UU选择的边可供选择的边1,2,3,4,5,6(2,5)(2,5,3)6124356616555634213125536442template void adjListGr
11、aph:prim(TypeOfEdge noEdge)const bool*flag=new boolVers;/设计一个布尔型的一维数组flag，flagi=ture 表示结点i在U中，否则表示结点i不在U中。/用两个一维数组lowCost和startNode来记录U中的结点到V-U中结点的权值最小的边。TypeOfEdge*lowCost=new TypeOfEdgeVers;/表示U中的结点到结点i的边的最小权值。int*startNode=new intVers;/表示从U中的哪一个结点出发到结点i的权值是lowCosti。edgeNode*p;TypeOfEdge min;int s
12、tart,i,j;for(i=0;i Vers;+i)/初始化，所有结点均不在U中，将flag的元素全部置成false；将lowCost的元素全部置成无穷大flagi=false;lowCosti=noEdge;Prim算法的实现算法的实现start=0;/将0作为第一个加入U中结点for(i=1;i next)if(!flagp-end&lowCostp-end p-weight)lowCostp-end=p-weight;/更新距离startNodep-end=start;flagstart=true;/将start加入U中min=noEdge;for(j=0;j Vers;+j)/寻找权
13、值最小的边if(lowCostj min)min=lowCostj;start=j;/将j加入Ucout (verListstartNodestart.ver ,verListstart.ver )t;lowCoststart=noEdge;/不再考虑这条边delete flag;delete startNode;delete lowCost;prim算法运行过程中算法运行过程中startNode和和lowCost数组的变化数组的变化 随机随机值随机随机值随机随机值随机随机值随机随机值随机随机值lowCoststartNode543210编号号0132456165556342651FFFFFF
14、visited453210编号编号T5564T26TT3TT 0 0 02225521时间复杂度时间复杂度n函数的主体是一个嵌套循环，外层循环执行|V|次，内层循环也执行|V|次。所以，Prim算法的时间复杂度是O（|V|2）。Does a linear-time MST algorithm exist?第第13章章 最小生成树最小生成树n生成树与最小生成树生成树与最小生成树nKruskal算法算法nPrim算法算法n算法的正确性算法的正确性算法的正确性算法的正确性n定理13.1：假设G=V,E 是一个连通图，U 是顶点集合V 的一个非空子集。若(u,v)是一条代价最小的边，且u U,v VU
15、则必存在一棵包括边(u,v)在内的最小生成树。定理的证明定理的证明n用反证法证明。n假定在图G=V，E 中，存在一棵不包括代价最小的边(u,v)在内的最小生成树，设其为T。将边(u,v)添加到树T，由于顶点u,v本来就是连通的，现在又增加了一条新的通路，所以便形成了一条包含边(u,v)的回路。因此，必定存在另一条边(u，v)，且u U,v V-U。为了消除上述的回路，可以将边(u ，v)删除。记为T T(u,v)(u ，v )。T 仍然包含V 的所有的顶点，而且这些顶点之间仍然是连通的，而且代价比T小。所以新的生成树T 将是代价最小的树。和原假设矛盾，原命题得证。总结总结n最小生成树是加权无
16、向连通图的权值和最小的极小连通子图，它有很重要的应用价值。n寻找最小生成树的两个经典算法：Kruskal算法和Prim算法，给出了它们在邻接表类中的实现。n最后证明了两个算法的正确性。Euclidean MSTnGiven N points in the plane,find MST connecting them,where the distances between point pairs are their Euclidean distances.Brute force.Compute N 2/2 distances and run Prims algorithm.Ingenuity.E
17、xploit geometry and do it in c N log N.Application:Models of naturehttp:/algo.inria.fr/broutin/gallery.htmlScientific application:clusteringnk-clustering.Divide a set of objects classify into k coherent groups.nDistance function.Numeric value specifying closeness of two objects.nGoal.Divide into clu
18、sters so that objects in different clusters are far apart.nApplications.nRouting in mobile ad hoc networks.nDocument categorization for web search.nSimilarity searching in medical image databases.nSkycat:cluster 109 sky objects into stars,quasars,galaxies.Single-link clusteringnk-clustering.Divide a
19、 set of objects classify into k coherent groups.nDistance function.Numeric value specifying closeness of two objects.nSingle link.Distance between two clusters equals the distance between the two closest objects(one in each cluster).nSingle-link clustering.Given an integer k,find a k-clustering that maximizes the distance between two closest clusters.Dendrogram of cancers in humannTumors in similar tissues cluster together.作业作业n简答题：14题n程序设计题：1题
免费区 
