MST-最小生成樹-文檔資料

1、1Minimum Spanning Tree 2Flight Path Problem3Flight Path Problem Consider the graph representing the airline connections between seven cities.abcdefg65916131215837the least flight pathsthe least cost Flight Path ProblemMinimum Spanning Tree4Minimum Spanning Tree Introduction Problem Definition Boruvk

2、as algorithm Conclusion5Introduction 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.

3、 6Problem 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.7Problem Definition A spanning tree in G is an acyclic subgraph

4、 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.8MSTP: The Minimal Spanning Tree problem (MSTP)is: Input: A

5、 weighted graphG=(v,e ,w). Output: The Unique spanning tree T that minimizes .)(ewTe9MSF 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 tre

6、es are spanning trees for the connected components of the graph G.10MSF 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

7、spanning tree if and only if the graph is connected. 11MSTa 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.12MST2nn Given an edge-weighted graph, this problem calls for finding a subtree spanning all the

8、 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? 13MSTP The MSTP is one of the best-studied problems in combinatorial opt

9、imization. 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.14Boruvkas algorithm The first MST algorithm was devised by Boruvka ,the algori

10、thm is based on the greedy strategy. The basic step in Boruvkas algorithm is the heart of many MST algorithms till to day. 15Boruvkas algorithmV 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 includin

11、g 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.16The process of Boruvkas algorithm abcdefgabcdefgabcdefg6591613121583756783122.For this graph, out of seven one-vertex ,two trees are create

12、d 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 con

13、nects these two trees, resulting in one spanning tree.3875617pseudocode: 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 tr

14、ee by combining t and the tree that includes u if such a tree does not exist yet;18Boruvkas 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 t