演算法與資料結(jié)構(gòu)AlgorithmandDataStructure

1、演算法 與資料結(jié)構(gòu)Algorithm and Data Structure- Graph Algorithm (Minimum Spanning Tree & Shortest Path)Minimum Spanning Tree 最小生成樹給定一個圖 G，其每條邊被賦予了一個weight 值，從其邊集 E 中選擇其中的一些邊，使得這些邊能夠連接所有的點(diǎn)，而且weight 總和是最少的。這就是所謂的最小生成樹問題，即Minimum Spanning Tree，簡稱 MST 。注意到為了使總 weight 最小，最後挑選出來的邊必不形成cycle，否則拿掉 cycle 上的其中一條邊仍符

2、合條件，且 weight 較??；又因?yàn)橐屗悬c(diǎn)相連，即選出來的邊使這個圖仍是connected，綜合以上（ connected且沒有 cycle），可知選出來的邊形成一個 tree。以下介紹兩個處理MST 的演算法 。注意兩者都只適用於undirected path，且邊權(quán)皆不為負(fù)值。兩個演算法的核心思想都是greedy，大家不妨好好體會。Prim s Algorithm O(m lgn)核心思想：由任一個點(diǎn)開始擴(kuò)展 MST ，每次選擇目前加進(jìn)來所需 cost 最小的點(diǎn)把它加入，並更新到每個點(diǎn)所需要增加的 cost 值。用 heap 來 implement。程序： MST-Prim ，回傳

3、MST 的 cost / 當(dāng)然也可以更改程式碼以紀(jì)錄 MST 切確的邊 MST-P RIM ()1 totalcost 02 for eachu V3 do u.cost 4 r .cost 0 / r is any node in V5 make V into a min-heap “Heap”determined by the value of cost6 while Heap is not empty7 do u EXTRACT -M IN (Heap)8totalcost totalcost + u.cost9for each vertexv Adju10do if v Heap an

4、d w(u, v) < v.cost / where w(u, v) is the weight of edge (u, v)11then v.cost w(u, v)12return totalcostKruskals Algorithm O(m lgm) = O(m lgn)核心思想：每次挑選 cost最小且其兩端點(diǎn)尚未相連的邊加入 MST，用 Disjoint Set 來 implement。程序： MST-Kruskal ，回傳 MST 的 cost / 當(dāng)然也可以更改程式碼以紀(jì)錄 MST 切確的邊MST-K RUSKAL ()1 totalcost 02 for eachv V

5、3 do MAKE -SET (v)4 sort the edges into non-decreasing order by weight5 for each edge u,( v) E, taken in non-decreasing order建中資訊培訓(xùn)講義( 七)- by kelvin6do if FIND -SET (u) FIND -SET (v)7then UNION (u, v)8totalcost totalcost + w(u, v)9return totalcost思考： 1. Prim-MST 和 Kruskal-MST 都使用 greedy approach，但其正

6、確性應(yīng)如何證明？2. Second-best MST問題：欲尋找總 cost 第二低的 Spanning Tree，應(yīng)如何達(dá)成？3. 更新 MST 問題：給定一已求出的 MST ，再加入新的邊，試求新的 MST ？Shortest Path 最短路徑顧名思義，最短路徑的問題就是給定一個圖 G，其每條邊有一個 cost 值，要求某兩點(diǎn)之間的一條 path，這條 path 的 cost 定義為其上所有邊的 cost 之和，而要使這條 path 的 cost 最小。以下介紹三種最短路徑的演算法，分別運(yùn)用在不同的狀況中。還有一種最短路徑算法是利用矩陣相乘，其時間複雜度並非最佳的（需 O(n3lgn)）

7、，但它有其他的應(yīng)用，值得去了解，但在此便略去不介紹。除此以外， dag 有 O(m)的最短路徑算法。在以下的演算法中，我們用一陣列 d 紀(jì)錄到每個點(diǎn)的最短距離； 紀(jì)錄每個點(diǎn)的祖先，即在 single-source shortest path中，它的上一個點(diǎn)是誰。以下則是兩個為求表達(dá)簡便的函式：Initialize-Single-Source (s)：初始化各頂點(diǎn)資料，其中s 為 source。INITIALIZE -SINGLE -SOURCE (S)1for each vertexv V2do dv 3v NIL4ds 0Relax (u, v)：檢查目前到 v 的最短距離是否小於經(jīng)由u 再

8、經(jīng)邊 (u, v)到 v 所需的距離小，若不是的話則更新到 v 的最短路徑為經(jīng)由u 點(diǎn)再經(jīng)邊 (u, v)到 v。RELAX (u, v)1 if dv > du + w(u, v)2 then dv du + w(u, v)3v uBellman-Ford Single-Source Shortest Path AlgorithmBellman-Ford 演算法用於比較一般的圖：當(dāng)圖的邊有可能出現(xiàn)負(fù)邊的時候。它可以再O(n3)的時間內(nèi)求出從某一起點(diǎn)s 出發(fā)，到其他每一點(diǎn)的最短距離。除此以外，它還有個很重要的應(yīng)用：發(fā)現(xiàn)負(fù)圈（negative cycle），即邊權(quán)總和為負(fù)的cycle。核心

9、思想：注意到兩點(diǎn)間的最短路徑只在兩點(diǎn)之間不存在negative cycle 的情況才有意義，因此對於一條有意義的最短路徑，是不會出現(xiàn)cycle 的，也就是每個點(diǎn)最多在這條path 上出現(xiàn)一次，因此一條shortest path最長為經(jīng)過 n 個點(diǎn)。若我們第 i 次更新能使 shortest path為經(jīng)過 i 個點(diǎn)的頂點(diǎn)其最短距離正確，那麼我們只要更新 n 次，即可達(dá)到目的求得由 s 到所有點(diǎn)的最短距離 。當(dāng)執(zhí)行第 n+1 次仍有更新時，就代表這圖中存在 negative cycle。建中資訊培訓(xùn)講義( 七)- by kelvin程序： Bellman-Ford 演算法/ 回傳值為 FALSE

10、 表示有 negative cycleBELLMAN -FORD (S)1 INITIALIZE -SINGLE -SOURCE (S)2 for eachu V3do for each edge u,( v) E4do RELAX (u, v)5for each edge u,( v) E6do if dv > du + w(u, v)7then return FALSE8return TRUEDijkstra s Single-Source Shortest Path AlgorithmDijkstra 是較快的 single-source shortest path演算法，但只適用

11、於沒有負(fù)邊的圖。它的時間複雜度在圖比較稀疏（ m = O(n2 / lgn)）的時候可以達(dá)到 O(m lgn)。某種程度上，它和 MST-Prim十分相似。核心思想：從起點(diǎn)s 出發(fā)，每次 greedy 地加入尚未到達(dá)的點(diǎn)終，目前距離s 最短的一個，加入後並更新與 s 相鄰的所有點(diǎn)其和s 的距離（即進(jìn)行 Relax）。程序： Dijkstra 演算法D IJKSTRA (S)1 INITIALIZE -SINGLE -SOURCE (S)2 Heap V3 while Heap ?4 do u EXTRACT -M IN (Heap)5for each vertexv Adju6do R(u,

12、v)ELAXFloyd-Warshall All-Pair Shortest Path AlgorithmFloyd-Warshall 是個容易撰寫求All-Pair Shortest Path 的 O(n3)演算法。核心思想：利用一條路徑上最多有 n 個頂點(diǎn)，歸納地更新各個 pair 之間的最短距離，保證第 k 次 iteration 後路徑上最大點(diǎn)邊號小於等於 k 者的點(diǎn)對，其最短距離會是正確的。思考： Floyd-Warshall 是很方便的 All-PairShortest Path 演算法，但對於一般的圖卻不是最快的，想想看，為什麼？有什麼辦法可以做得比Floyd-Warshall 更好？程序： Floyd-Warshall 演算法FLOYD -WARSHALL ()1