MST-最小生成树课件.ppt

Minimum Spanning Tree,-,Minimum Spanning Tree,Flight Path Problem,-,Flight Path Problem-,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 least cost,Flight Path Problem,Minimum Spanning Tree,-,Flight Path ProblemConsider th,Minimum Spanning Tree,IntroductionProblem DefinitionBoruvkas algorithmConclusion,-,Minimum Spanning TreeIntroduct,Introduction,The minimum 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,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,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,MSTP:,The Minimal Spanning Tree problem (MSTP)is: Input: A weighted graphG=(v,e ,w). Output: The Unique spanning tree T that minimizes .,-,MSTP:The Minimal Spanning Tree,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,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,MST,a spanning tree: ahbcigfedthe weights of this tree: 8+11+8+2+6+2+10+9=56.minimal spanning tree: abcifghdethe weights of MST: 4+8+7+2+4+9+2+1=3756.,-,MSTa spanning tree:,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,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,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,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 vcreate 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,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,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,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 log n).,-,Boruvkas algorithm Does th,Conclusion,Boruvkas method lends itself very nicely to parallel processing, since for each tree, a minimum edge has to be found independently.,-,ConclusionBoruvkas method le,Thats all!Thank you!,-,Thats all!Thank you!,