演算法與資料結構 Algorithm and Data Structure

《演算法與資料結構 Algorithm and Data Structure》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、演算法與資料結構AlgorithmandDataStructure-GraphAlgorithm(MinimumSpanningTree&ShortestPath)MinimumSpanningTree最小生成樹給定一個圖G，其每條邊被賦予了一個weight值，從其邊集E中選擇其中的一些邊，使得這些邊能夠連接所有的點，而且weight總和是最少的。這就是所謂的最小生成樹問題，即MinimumSpanningTree，簡稱MST。注意到為了使總weight最小，最後挑選出來的邊必不形成cycle，否則拿掉cycle上的其中一條邊仍符合條件，且weight較小；又因為要讓所有點相連，即選

2、出來的邊使這個圖仍是connected，綜合以上（connected且沒有cycle），可知選出來的邊形成一個tree。以下介紹兩個處理MST的演算法。注意兩者都只適用於undirectedpath，且邊權皆不為負值。兩個演算法的核心思想都是greedy，大家不妨好好體會。Prim’sAlgorithm–O(m×lgn)核心思想：由任一個點開始擴展MST，每次選擇目前加進來所需cost最小的點把它加入，並更新到每個點所需要增加的cost值。用heap來implement。程序：MST-Prim，回傳MST的cost//當然也可以更改程式碼以紀錄MST切確的邊MST-Prim()1to

3、talcost← 02foreachuÎV3dou.cost ← ¥4r.cost← 0//risanynodeinV5makeVintoamin-heap“Heap”determinedbythevalueofcost6whileHeapisnotempty7 dou ← Extract-Min (Heap)8totalcost ← totalcost+u.cost9foreachvertexvÎAdj[u]10 doifvÎHeapandw(u, v)

4、)12returntotalcostKruskal’sAlgorithm–O(m×lgm)=O(m×lgn)核心思想：每次挑選cost最小且其兩端點尚未相連的邊加入MST，用DisjointSet來implement。程序：MST-Kruskal，回傳MST的cost//當然也可以更改程式碼以紀錄MST切確的邊MST-Kruskal()1totalcost← 02foreachvÎV3doMake-Set(v)4sorttheedgesintonon-decreasingorderbyweight建中資訊培訓講義(七)-bykelvin5foreachedge (u,v)ÎE,tak

5、eninnon-decreasingorder6doifFind-Set(u)¹Find-Set(v)7 thenUnion(u,v)8totalcost ← totalcost+w(u, v)9returntotalcost思考：1. Prim-MST和Kruskal-MST都使用greedyapproach，但其正確性應如何證明？2. Second-bestMST問題：欲尋找總cost第二低的SpanningTree，應如何達成？3. 更新MST問題：給定一已求出的MST，再加入新的邊，試求新的MST？ShortestPath最短路徑顧名思義，最短路徑的問題就是給定一個圖G，其每

6、條邊有一個cost值，要求某兩點之間的一條path，這條path的cost定義為其上所有邊的cost之和，而要使這條path的cost最小。以下介紹三種最短路徑的演算法，分別運用在不同的狀況中。還有一種最短路徑算法是利用矩陣相乘，其時間複雜度並非最佳的（需O(n3lgn)），但它有其他的應用，值得去了解，但在此便略去不介紹。除此以外，dag有O(m)的最短路徑算法。在以下的演算法中，我們用一陣列d[]紀錄到每個點的最短距離；p[]紀錄每個點的祖先，即在single-sourceshortestpath中，它的上一個點是誰。以下則是兩個為求表達簡便的函式：Initialize-Sing

7、le-Source (s)：初始化各頂點資料，其中s為source。Initialize-Single-Source(s)1foreachvertexvÎV2dod[v] ← ¥3 p[v] ← NIL4d[s] ← 0Relax (u,v)：檢查目前到v的最短距離是否小於經由u再經邊(u,v)到v所需的距離小，若不是的話則更新到v的最短路徑為經由u點再經邊(u,v)到v。Relax(u, v)1ifd[v]>d[u]+w(u,v)2thend[v] ←