MST-最小生成树课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,-,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,-,*,M,inimum,S,panning,T,ree,-,Minimum Spanning Tree,1,Flight Path Problem,-,Flight Path Problem-,2,Flight Path Problem,Consider the graph representing the airline connections between seven cities.,a,b,c,d,e,f,g,6,5,9,16,13,12,15,8,3,7,the least flight paths,the leas,t,cost,Flight Path Problem,M,inim,um,S,panning,T,ree,-,Flight Path ProblemConsider th,3,M,inimum,S,panning,T,ree,Introduction,Problem Definition,Boruvkas algorithm,Conclusion,-,Minimum Spanning TreeIntroduct,4,Introduction,The,minim,um,spanning tree problem,is one of the oldest and most basic graph problems in theoretical computer science.,Its history dates back to Boruvkas algorithm in 1926 and till to day it is a extensively researched problem with new breakthroughs only recently.,-,Introduction The minimu,5,Problem Definition,All the graphs in this report are,finite,simple,and,undirected,.,We denote by,n,the number of vertices,m,the number of edges in a graph,G=(V,E),.,Our graphs are weighted,w(e),denoting the distinct weight of the edge,e,.,-,Problem DefinitionAll the grap,6,Problem Definition,A spanning tree,in G is an acyclic,subgraph of G that,includes every vertex,of G and is,connected,;,every spanning tree has exactly,n-1,edges.,The weight of a tree is defined to be the,sum of the weights of its edges,.,A minimum spanning tree(MST)is a spanning tree of,minimum weight,.,-,Problem DefinitionA spanning t,7,MSTP,:,The,Minimal Spanning Tree problem,(MSTP)is:,Input:,A weighted graph,G=,(,v,e,w,).,Output:,The Unique spanning tree T that minimizes,.,-,MSTP:The Minimal Spanning Tree,8,MSF,When the input graph G is,not connected,a spanning tree does not exist and we generalize the notion of a minimum spanning tree to that of a,minimum spanning forest,(MSF).,A spanning forest is a forest whose trees are spanning trees for the connected components of the graph G.,-,MSFWhen the input graph G is n,9,MSF,So when G is not connected we find the minimal spanning forest MSF:,A set of trees,one in each of the connected component of G,each tree being a minimal spanning tree of the graph induced by the component.,A spanning forest is a spanning tree,if and only if the graph is connected.,-,MSFSo when G is not connected,10,MST,a spanning tree,:ahbcigfed,the weights of this tree:8+11+8+2+6+2+10+9=56.,minimal spanning tree:abcifghde,the weights of MST:4+8+7+2+4+9+2+1=3756.,-,MSTa spanning tree:,11,MST,Given an edge-weighted graph,this problem calls for finding a subtree spanning all the vertices,whose total weight is,minimal,.,For a,n,-degree complete graph,there are,spanning trees.,Then the central open question is:,Does there exist a linear time deterministic algorithm that finds the minimal spanning tree?,-,MSTGiven an edge-weighted grap,12,MSTP,The MSTP is one of the best-studied problems in,combinatorial optimization,.,A variety of algorithms have been developed for this problem,most of which are based on a,greedy strategy,and run in,near-linear O(m log n)time,e.g.,Boruvkas algorithm,Kruskals algorithm,Prims algorithm,.,-,MSTPThe MSTP is one of the bes,13,Boruvkas algorithm,The first MST algorithm was devised by Boruvka,the algorithm is based on the,greedy strategy,.,The basic step in Boruvkas algorithm is the heart,of many MST algorithms till to day.,-,Boruvkas algorithm The f,14,Boruvkas algorithm,we start with,one-vertex trees,;,for each vertex v,we look for an edge(vw)of minimum weight among all edges outgoing from v,create small trees by including these edges.,Then,we look for edges of minimal weight that can connect the resulting tree to larger trees.,The process is finished when one tree is created.,-,Boruvkas algorithmwe start wi,15,The process of,Boruvkas algorithm,a,b,c,d,e,f,g,a,b,c,d,e,f,g,a,b,c,d,e,f,g,6,5,9,16,13,12,15,8,3,7,5,6,7,8,3,12,2.,For this graph,out of seven one-vertex,two trees are created because,for vertices a and c,edge(ac)is chosen,for vertex b,edge(ab)is chosen,for vertex d,edge(df)is chosen,for vertex e,edge(eg)is chosen,and for vertices f and g,edge(fg)is chosen.,3.,for the tree(abc)and the tree(defg),edge(cf)is selected,since it is the shortest edge that connects these two trees,resulting in one spanning tree.,3,8,7,5,6,-,The process of Boruvkas algor,16,pseudocode,:,BoruvkaAlgorithnm(weighted connected undirected graph),make each vertex the root of a one-node tree;,While there is more than one tree,For each tree,t,e=minimum weight edge(,vu,)where,v,is included in,t,and,u,is not;,create a tree by combining,t,and the tree that includes,u,if such a tree does not exist yet;,-,pseudocode:BoruvkaAlgorithnm,17,Boruvkas algorithm,Does this algorithm run in a linear time?,Boruvkas algorithm thus reduces the MST problem in an,n,-vertex graph with,m,edges to the MST problem in an,(n/2),-vertex graph with at most,m,edges.,The time required for the reduction is only,O(m+n),.,It follows that the worst-case running time of this algorithm is,O(m l