MST-最小生成樹-文檔資料_第1頁
MST-最小生成樹-文檔資料_第2頁
MST-最小生成樹-文檔資料_第3頁
MST-最小生成樹-文檔資料_第4頁
MST-最小生成樹-文檔資料_第5頁
已閱讀5頁,還剩15頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論