--- # System prepended metadata title: 演算法 期末考 筆記 tags: [演算法] --- --- tags: 演算法 --- # 演算法 期末考 筆記 ![](https://i.imgur.com/fnwPBPh.png =500x) ### 課本習題的解答多看有益身心健康 https://walkccc.me/CLRS/Chap24/24.3/ https://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html # ch12 Binary Search Trees - INORDER_TREE_WALK(x) - Θ(n) - 補充：Inorder、Preorder、Postorder tree walk ![](https://i.imgur.com/MR8wiWv.png) - TREE_SEARCH(x, k) - O(h) - ITERATIVE_SEARCH(x, k) - 例題12.2-1 哪個組合不可能是BST search 363的過程？ ![](https://i.imgur.com/5TLsZPJ.png) - 參考答案：c、e是錯的 ![](https://i.imgur.com/HtjqxyG.jpg) - 例題12.2-4 Professor Bunyan發現一個屬性 search path左邊的所有節點a < search path上的所有的節點b < search path右邊的所有節點c 解釋是否正確？ ![](https://i.imgur.com/0OO71on.png) - 參考答案：不正確 (以下範例假設要search key 4) ![](https://i.imgur.com/FKCsiaw.jpg) - TREE_MINIMUM(x) - O(h) - TREE_MAXIMUM(x) - O(h) - TREE_SUCCESSOR(x) 1. 如果x.right不是null，先找x右子樹的最小值TREE-MINIMUM(x.right) (ex.15的successor為17) ![](https://i.imgur.com/blh1iVN.png) 3. 如果x.right是null，往上找x的祖先y，直到找到第一個y的左子樹是x的祖先 (ex.13的successor為15) ![](https://i.imgur.com/nFN5qhJ.png) - The dynamic-set operations：O(h)(tree of height h) - 例題12.2-5 證明一個node有兩個小孩，則他的successor沒有左邊小孩，他的predecessor沒有右邊小孩 ![](https://i.imgur.com/8PRtX0S.png) - 參考解答： 假設node x有兩個小孩 x的successor是x的right tree中最小的，不可能還有左邊小孩 x的predecessor是x的left tree中最大的，不可能還有右邊小孩 - Tree-Insert(T, z) - O(h) - Tree-Delete(T, z) - O(h) - Transplant(T, u, v) - Replace the subtree of u with the subtree of v - TREE_MINIMUM(x) Deletion 1. z has no children 2. z has just one child a. 若z.left = NIL，z.right取代z b. 若z.right = NIL，z.left取代z 4. z has two children **取y為Tree-Minimum(z.right)** c. 若y.p=z，y取代z，z的左子樹變成y的左子樹 d. 若y.p!=z，先將y的右子樹取代y，再將y取代z，z的左子樹變成y的左子樹 (這裡要注意y是z的右子樹的最小值，不會有left，所以圖上y.left都畫NIL) ![](https://i.imgur.com/1gs8yPz.png) The dynamic-set operations：O(h) # ch13 Red-Black Trees - 13.1 Properties of red-black tree - 在最壞的情況下花費O（log n）時間 - 紅黑樹是一種BST額外增加一個bit紀錄顏色(紅/黑) - 透過顏色標記的限制方式，讓the root to a leaf的path不會超過其他path的兩倍，使BST大約平衡 - 符Red-Black Tree的條件(可能會考如何判斷是不是紅黑樹 ex.課本例題13.1-2) 1.每個點不是紅就是黑 2.root是黑色 3.所有leaf(NIL)是黑色 4.如果某個節點是紅色，那他的小孩一定是黑色 5.以某個節點為起點，往下到所有葉子的的路徑上的黑點數量相同 ![](https://i.imgur.com/ikjEB3C.png) - Lemma13.1：A red-black tree with n internal nodes has height at most **2lg(n+1)**. - 13.2 Rotations - The code for RIGHT-ROTATE is symmetric. - Both LEFT-ROTATE and RIGHT-ROTATE run in O(1) time. ![](https://i.imgur.com/XWwny7x.png) - 可能會考如何畫rotation前後如何畫圖(ex.如下圖) ![](https://i.imgur.com/Um8UQFP.png) - 13.3 Insertion - O(lg n) - Insert Node的方法和Binary Search Tree大致相同相同，假設insert Node z，最後要分別做以下動作讓樹的結構還是一個RB-Tree - z.left=NIL - z.right=NIL - z.color=Red - RB-INSERT-FIXUP(T, z) - RB-INSERT-FIXUP(T, z) ![](https://i.imgur.com/E8B9nx3.png) - Insert後如果z的parent是Red時 1. 如果z的parent是z的爺爺的左邊小孩(z.p=z.p.p.left)，有三種情況與處理方式 **Case 1: z’s uncle y is red** ToDo：將z的parent和z的uncle顏色換成black，把z的爺爺換成red，z變成的爺爺(z=z.p.p)，如圖a到圖b的過程 **Case 2: z’s uncle y is black and z is a right child** ToDo：z變成z的parent(z=z.p)，進行LEFT-ROTATE(T, z)，如圖b到圖c的過程 **Case 3: z’s uncle y is black and z is a left child** ToDo：將z的parent變成黑色，將z的爺爺變成紅色，再進行RIGHT-ROTATE(T, z.p.p)，如圖c到圖d的過程 **重要：最後要把root圖黑(無論如何root一定要是黑色!!!)** 2. 如果z的parent是z的爺爺的右邊小孩(z.p=z.p.p.right)的三種情況與處理方式，只要把上面情況的left/right互換即可 - 要隨時注意z和y的位置變化比較好理解 ![](https://i.imgur.com/7ZOkrbx.png) - 例題13.3-2 Show the red-black trees that result after successively inserting the keys 41; 38; 31; 12; 19; 8 into an initially empty red-black tree. - 參考答案： ![](https://i.imgur.com/GPlRkYx.png) - 13.4 Deletion - O(lg n) - RB-DELETE(T,z) - 如果被刪除的節點是紅色 => RB tree的平衡還在 - **如果被刪除的節點是黑色 =>會違反RB Tree的原則，要執行RB-DELETE-FIXUP** - RB-DELETE-FIXUP(T, x) ![](https://i.imgur.com/Ihcc5Cg.png) -如果x不是root && x是黑色 - 觀念：不管x點是紅還是黑，y少掉的黑帶在x身上 => 只要是x都多帶一個黑 1. 如果x是x的parent的左邊小孩(x=x.p.left)，有四種情況與處理方式 **Case 1: x’s sibling w is red** ToDo：w塗黑，x的parent塗紅，LEFT-ROTATE(T, x.p)，new w為x.p.right，如圖a **Case 2: x’s sibling w is black, and both of w’s children are black** ToDo：w塗紅，new x為x.p，如圖b **Case 3: x’s sibling w is black, w’s left child is red, and w’s right child is black** ToDo：w塗紅，w.left塗黑，RIGHT-ROTATE(T,w)，new w為x.p.right，如圖c **Case 4: x’s sibling w is black, and w’s right child is red** ToDo：w塗x的parent的顏色，x的parent塗黑，LEFT-ROTATE.T(x,p)，new x為T.root，如圖d **重要：最後要把x(root)塗黑(無論如何root一定要是黑色!!!)** 2. 如果x是x的parent的右邊小孩(x=x.p.right)，有四種情況與處理方式，只要把上面情況的left/right互換即可 - 要隨時注意x和w的位置變化比較好理解 ![](https://i.imgur.com/GaBu1uw.png) ![](https://i.imgur.com/yRP7wcX.png) - 例題13.4-3 依照13.3-2的結果依序刪除8; 12; 19; 31; 38; 41. - 參考答案： ![](https://i.imgur.com/zy2FVqg.png) # ch18 B-Trees ![](https://i.imgur.com/qtrPvV3.png) - B-Tree特性 - 每一棵B-Tree都需要在建立前指定好minimum degree ≧ t 。 - 樹上的每個節點內存放最少t-1個keys，最多2t-1個Keys。 - Root Node較為特殊，允許存放最少1個Key，最多2t-1個Keys。**如果Node已經有2t-1個keys稱為full。** - 若節點有n個keys，則有n+1個小孩 - 每個節點上的Keys都是以升序排列，相隔的兩Key，K1、K2，之間的任一子節點上的任一Key，其值必落在 K1~K2 之間。 - 所有葉節點（Leaf Node）的深度（Depth）必定相同(= tree's height h)。 ![](https://i.imgur.com/wPpSFbE.png) - Search - Run Time ![](https://i.imgur.com/p2ngJVi.png) - B-Tree 的 Search 從 Root Node 開始，比對目標 Key 與所在節點上的 Key 的值。若目標 Key 的值： 1. 小於最小Key，就往節點上最左方的子節點往下移動。 2. 落在某二鄰近 Key 之間，就往此二鄰近 Key 之間的子節點往下移動。 3. 大於最大Key，就往節點上最右方的子節點往下移動。 - 重複直到找到相符或找到葉節點還找不到為止。 - Creating an empty B-tree - O(1) - Insert　（從上往下跑，遇到滿的就炸開）（滿：2t-1） - Run Time ![](https://i.imgur.com/p2ngJVi.png) - 從root沿路scan，**只要遇到full就先split** - t=3為例，Insert B、Q、L、F ![](https://i.imgur.com/Vsjma4b.png) - Delete　（從上往下跑，遇到不足的就合起來）（不足：t-1） - Run Time ![](https://i.imgur.com/p2ngJVi.png) - 從root沿路掃到下面delete key的處理方式： - Case1：如果key所在的節點是葉子，直接delete，如圖b - Case2：如果key所在的節點為 Internal Node a.如果key左邊指標指到的小孩數量為t，將小孩最大值(Predecessor)取代key的位置，如圖c b.如果key右邊指標指到的小孩數量為t，將小孩最小值(Successor)取代key的位置 c.如果兩邊指標指到的小孩數量都不足t，將key和兩個小孩合併後delete key，如圖d - Case3：key經過的Node稱為x.c，如果x.c只有t-1個Key，要先將x.c補滿到t個key a.如果x.c左邊兄弟有t個key，將x.c parent key給x.c，將左邊兄弟最右邊key給x.c parent，左邊兄弟的右邊小孩給x.c。如果x.c右邊兄弟有t個key，將x.c parent key給x.c，將右邊兄弟最左邊key給x.c parent，右邊兄弟的左邊小孩給x.c。如圖f b.如果兩邊兄弟都只有t-1個key，將x.c與左邊兄弟(或右邊兄弟)與他們中間的parent key做合併，處理好後在往下走進行delete key，如圖e - t=3為例，Delete F、M、G、D、B ![](https://i.imgur.com/WVAC9Lw.png) ![](https://i.imgur.com/jUs1gx5.png) # ch19 Fibonacci Heaps - Structure of Fibonacci heaps ![](https://i.imgur.com/7z03l4B.png) - 上層為root list，root list最小的點為H.min - 曾經失去一個小孩就會變成黑色(H.mark=true) - 變成別人小孩就會變成白色(H.mark=false) - Potential function - ![](https://i.imgur.com/e4iieNq.png) = number of trees + 2 * number of marks - Maximum degree - D(n) = O(lg n) → 任何人的小孩個數頂多lgn個 - Creating a new Fibonacci heap - O(1) - Make-Fib-Heap() - Inserting a node - O(1) - Fib-Heap-Insert(H, x) - 將key insert到root list，通常放在H.min的左邊，如果新增的key比較小就指定為H.min，以下為insert key 21的範例 ![](https://i.imgur.com/04ncyZq.png) - Finding the minimum node (找最小值) - O(1) - Minimum(H) - 最小值在H.min - Uniting two Fibonacci heaps (將H1、H2合併) - O(1) - Fib-Heap-Union(H1, H2) - 將H1、H2的root list連在一起，再比較H1.min和H2.min誰比較小，指定為新的Heap的H.min - Extracting the minimum node(取出最小值) - O(D(n)) = O(lg n) - Fib-Heap-Extract-Min(H) - z=H.min，將z的兒子都放到root list，取出z，並指定z的右邊root為新的H.min，如圖b - 從H.min往右使用一個陣列紀錄degree，若遇到將相同degree的root就做合併，小的當root，一直到沒有相同degree的root，如圖c到l - 將root list最小值指定為H.min，如圖m ![](https://i.imgur.com/tqXoS3C.png) ![](https://i.imgur.com/lbKxe6q.png) - Decreasing a key (把某個key的值變小) - O(1) - Fib-Heap-Decrease-Key(H, x, k) - 用途：將key變小，就可以用Extracting the minimum node方法將key刪除 - 步驟： ***每人最多失去一個孩子，若超過，移到root list** 1. 將key值變小後放到root，如果key原本的parent為白色(H.mark=false)，則塗成黑色，如圖b、c 2. 如果放到root的key原本的parent是黑色(H.mark=true)，也要放到root，如圖d 3. 重新指定H.min - 以下舉例46→15和35→5 ![](https://i.imgur.com/QMTVx9y.png) - Deleting a node - O(D(n)) = O(lg n) - FIB-HEAP-DELETE(H, x) - 將要刪除的key值變成負無限大 → FIB-HEAP-DECREASE-KEY(H,x,-∞) - 取出最小值後刪除 → FIB-HEAP-EXTRACT-MIN(H) # ch21 Data Structures for Disjoint Sets - Disjoint Sets：「互斥集」的意思是一堆集合們，大家擁有的元素都不相同，也就是說**這些集合們之間都沒有交集**。 - ex. A = {1,2,3} B={4,5,6} C={1,2,7}，則AB構成Disjoint Sets，AC不構成Disjoint Sets。 - Disjoint Set的操作： - MAKE-SET(x)：MAKE 建立一個只含x的set。因為互斥，所以x不能在其他集合出現過。 - UNION(x,y)：Union 是將兩個含有x和y的集合合併。 - FIND-SET(x)：Find 則是查詢某個元素所在的集合。 - 參數定義： - m：總共有m個opterations(make、union、find) - n：其中包含n個make operations - CONNECTED-COMPONENTS：一開始將每個點單獨看成不同的集合，對於每一條edge(u,v)，假設u,v在不同的集合之內，就將包含他們的集合聯集起來，最後看剩下幾個集合，就是有幾個connected component。 - 例題21.1-1 ![](https://i.imgur.com/dKXmXLF.png) - 參考答案： ![](https://i.imgur.com/bvaj7u9.png) - Linked List v.s. rooted tree | | linked List | rooted tree | | -------- | ----------- | ----------- | | make | O(1) | O(1) | | union | O(n^2) 費時 | O(α(n)) 快 | | find | O(1) 快 |O(mα(n)) 慢→快| - α(n)是Ackermann’s function的反函數，其成長速率非常慢。在所有可能的應用中，α(n) <= 4 (近乎常數頂多是4) - rooted tree的find function本來很慢改善後可以變快→O(mα(n)) worst case - Linked-list representation of disjoint sets - A simple implementation of union(不考慮每個set的長度) - 以序列中第一個元素當作代表人(representative)。 ![](https://i.imgur.com/3CrkTqn.png) ![](https://i.imgur.com/t9Mtd0u.png) - A weighted-union heuristic(考慮每個set的長度，短的併到長的) - 每一個representative存放其代表的序列的長度。 - 把較短的序列附加在較長的序列之後。(可以節省union時間) - Disjoint-set forests (rooted tree) - Tree的root為代表人(representative)。 ![](https://i.imgur.com/o3qCFFm.png) - 改善running time的方法： - **Union by rank**: 由較小高度的的tree的root連到較大的tree的root。 - **Path compression**: 在執行Find-Set(x)過程中，把所有經過的node都掛在root底下。 (壓縮) ![](https://i.imgur.com/nIQYIyx.png) # ch22 Elementary Graph Algorithms (初級圖演算法) ## 22.1 Representations of graphs(圖形表示) 1. 無方向(Undirected graph: no orientation is specified) 2. 有方向(Directed graphs: Oriented, the adjency matrix is not necessarily symmetric) 3. 矩陣 [adjacency-matrix representation (dense)] 4. 串列 [adjacency-list representation (sparse)] - 無方向：矩陣&串列表示法 ![](https://i.imgur.com/oksqBU5.png =400x) - 有方向：矩陣&串列表示法 ![](https://i.imgur.com/uZYtMho.png =300x) ## 22.2 Breadth-first Search (BFS:廣度優先) - BFS(G,s)：圖形G中，計算*s*到其他點的最短距離 - Analysis Complexity:O(V+E) - 應用：**Queue(先進先出)**；ENQUEUE(Q,s)：s放入Queue中；DNQUEUE(Q)：Queue中取值 - 屬性 - color：顏色註記[白色（未搜尋過），灰色（已搜尋過，丟Queue中）和黑色（搜尋完成，沒有相鄰點，移出Queue）] - d：距離(distance ) - π：前一個節點 - adj[u]：*u*點相鄰的點集合 ![](https://i.imgur.com/XZifbQO.png =300x) - line:1-8，初始化 - line:1-4，*s*外的點給予初值 - line:5-7，*s*點給予初值 - line:8，Queue給予初值 - line:9，起點s放入Queue中，透過Queue的特性完成廣度優先搜尋 - line:10，持續執行到Queue為空為止 (loop level1) - line:11，取出Queue的值為*u* - line:12，將*u*相鄰的點依序取出為*v* (loop level2) - line:13-17，若*v*顏色為白色者(未搜尋過)則註記為灰色，將該點*v*的距離(*d*)紀錄為*u*的距離加1，並留下v的前一個節點(*π*)為*u*後放入放入Queue中 - line:18，將u標記為黑色視為以搜尋完成所有相鄰的點 ![](https://i.imgur.com/4lIREN9.png) > 參考網址：Graph: Breadth-First Search(BFS，廣度優先搜尋) > http://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html - Shortest paths：當我們用BFS找端點對端點最短路時，從出發點開始，第一次遍歷到終點時過的那條路徑就是最短的路徑。 ## 22.3 Depth-First Search (DFS:深度優先) - Complexity:O(V+E) - 應用：**Recursion**的方式做深度優先持續往下鑽 - 屬性 - color：顏色註記[白色（未拜訪過），灰色（已拜訪過，可拜訪相鄰的點）和黑色（拜訪完成，沒有相鄰點可拜訪）] - d：發現(discovered) - f：完成(finished) - π：前一個節點 - adj[u]：*u*點相鄰的點集合 ![](https://i.imgur.com/5BWUNdu.png) - line:1-3，loop所有點初始化 - line:4，time初值 - line:5-7，loop所有點*u*，判斷白色(未拜訪過)的點後執行[DFS-VIST(G,u) Recursion]recurse ![](https://i.imgur.com/vig8dZc.png) - line:1-3，透過time累計拜訪次數，並將目前次數賦予目前拜訪的點 *u.d* 後將該點顏色註記為灰色 - line:4-7，loop所有*u*相鄰的點*v*，判斷白色(未拜訪過)的點，紀錄前一個節點(*π*)為*u*後執行[DFS-VIST(G,v) Recursion]recurse - Classification of edges: 1. Tree edges：2-4以外的邊。 2. Back edges(B)：經過的邊拜訪到的點為灰色時。 3. Forward edges(F)：經過的邊拜訪到的點為黑色時。 4. Corss edges(C)：不同component的edge。 - ![](https://i.imgur.com/BGOQKsY.png) > 參考網址：Graph: Depth-First Search(DFS，深度優先搜尋) > http://alrightchiu.github.io/SecondRound/graph-depth-first-searchdfsshen-du-you-xian-sou-xun.html ## 22.4 Topological Sort (拓撲排序) - 有方向無循環(directed acyclic graph) - 正確的Topological Sort可能不止一種 ![](https://i.imgur.com/iz9agg9.png) - 透過DFS(G)計算各節點完成時間(標記黑色的順序) - 將各節點完成時間由大到小排序 ![](https://i.imgur.com/6wrfE37.png) - 做DFS下鑽到最後一個點時，因沒有相鄰的而返回表示無循環；反之，有相鄰的點但皆為灰色點而返回表示有循環 > 參考網址：Graph: 利用DFS尋找DAG的Topological Sort(拓撲排序) > http://alrightchiu.github.io/SecondRound/graph-li-yong-dfsxun-zhao-dagde-topological-sorttuo-pu-pai-xu.html ## 22.5 Strongly connected components (強關聯元件) - 有向圖 - Complexity:O(V+E) ![](https://i.imgur.com/oGtrGPQ.png) - 透過DFS(G)計算各節點完成時間(*u.f*：標記黑色)[如下圖(a)] - 將圖的所有方向顛倒產生G^T^(Transpose of Graph)[如下圖(b)] - 透過DFS(G^T^)計算，DFS主程式的loop按line:1的完成時間(*u.f*)遞減順序執行 - line:3運行DFS主程式的loop每判斷為白色(未拜訪過)做recurse為一個component(each tree in the depth-first forest) ![](https://i.imgur.com/tXoMDwg.png) - component graph一定是directed acyclic graph(DAG)。 > 參考網址：Graph: 利用DFS尋找Strongly Connected Component(SCC) > http://alrightchiu.github.io/SecondRound/graph-li-yong-dfsxun-zhao-strongly-connected-componentscc.html # ch23 Minimum Spanning Trees (MST，最小生成樹) - 從圖中找出最小生成樹(MST)的問題 - 無向圖(undirected graph)，端點都有連接(connected)且有權重(weight)的圖，希望找出沒有循環並能連接所有點的子集合，且總權重要是最小的。 - Spanning Tree：沒有循環且連結所有點 ![](https://i.imgur.com/5zetc1H.png) ## 23.1 Growing a minimum spanning tree ![](https://i.imgur.com/stXWyS7.png) - line:1，A為邊的空集合，初始化 - line:2-4，A集合還未形成spanning tree下，持續loop找出一個對A集合是**安全**(**safe**)的邊(edge)後，聯集(union)到A集合中。 - **安全**(**safe**)定義：區分點(vertex)的集合和邊(edge)的集合，演算法中為邊(edge)的集合，而以下定義有部分在說點的集合。 - 名詞解釋： - cut(切割)：點(vertex)集合，分成兩部分的partition(分割)，spanning tree用的點集合 - crosses(交叉)：邊(edge)集合，一個邊(edge)串連cut的partition與圖其他點的邊，稱為crossing edge - respects(尊敬)：Set A中沒有任何一條edge是crossing edge - light edge(輕量邊)：crossing edge中權重(weight)最小的邊 - 定理1：符合四點表示**安全**(**safe**) 1. 圖要相連、有權重且無方向的圖 2. 集合A是MST的子集合 3. 集合A要有respects 4. line:3找的邊要為crossing edge且要是light edge - 推論2：如下集合A的connected component也符合**安全**(**safe**) 1. 同定理1,2點的情境 2. 集合A中的數個connected component皆可視為一棵樹 3. 連結各個connected component的light edge(同定理4) > 參考網址：Minimum Spanning Tree：Intro(簡介) > http://alrightchiu.github.io/SecondRound/minimum-spanning-treeintrojian-jie.html - Kruskal and Prim summary - Kruskal’s algorithm：所有邊找權重由小到大完成MST - Prim’s algorithm：從一個起始點開始往外找每個點相鄰的最小權重的邊 ## 23.2 Algorithms of Kruskal and Prim ### Kruskal’s algorithm ![](https://i.imgur.com/srzVg4F.png) - line:1-3，初始化 - line:4，把圖的所有邊(edges)以權重(weight)由小到大做排序 - line:5-8，loop所有邊(edges)依權重由小到大運行，判斷邊 *u* 和 *v* 在不同集合中，便將邊(u,v)放入A集合中，*u* 和 *v* 的點集合聯集 ![](https://i.imgur.com/X8bY3rC.png) ![](https://i.imgur.com/jhTakAc.png) > 參考網址：Minimum Spanning Tree：Kruskal's Algorithm > http://alrightchiu.github.io/SecondRound/minimum-spanning-treekruskals-algorithm.html ### Prim’s algorithm ![](https://i.imgur.com/gldagMY.png) - line:1-4，初始化 - line:5，所有點丟入a min-priority queue Q based on a key attribute - line:6-7，Queue中取出最小的做為 *u* 至Queue取空為止 (loop level 1) - line:8-11，所有 *u* 的相鄰的點依序取出為 *v* (loop level 2)，判斷 *v* 點仍存在於Queue中，且 *u* 到 *v* 之間的權重找最小者 ![](https://i.imgur.com/TAbgIxD.png) > 參考網址：Minimum Spanning Tree：Prim's Algorithm > http://alrightchiu.github.io/SecondRound/minimum-spanning-treeprims-algorithm.html # ch24 Single-Source Shortest Paths - shortest-path weight δ(u,v) from u to v ![](https://i.imgur.com/l8wXmer.png) - v.d = d[v]指的是目前到v點的距離 v.π指的是v的前一個點(predecessor) - single-source shortest-paths problem與他的三種變形 (Variants) 1. single-source shortest-paths problem 從單一vertex，抵達Graph中其餘所有vertex之最短路徑。(一對多) 2. Single-destination shortest paths problem 從Graph中的每一個vertex抵達某個特定vertex之最短路徑，剛好與第1種問題的子問題相反。(多對一) 3. Single pair shortest path problem 從單一vertex，抵達某個特定vertex之最短路徑，此為第1種問題的子問題。(一對一) 4. All-pair shortest paths problem Graph中的所有vertex抵達其餘所有vertex之最短路徑。(多對多) - 若把每一個vertex都當作起點，即可利用第1種問題之方法解決。 - 不過Ch25介紹的**Floyd-Warshall Algorithm**有更好的答案。 - Optimal substructure of a shortest path - Optimal substructure定義：原問題的最佳解是由其子問題得的最佳解算出來的 - Lemma 24.1. Subpaths of shortest paths are shortest paths(最短路徑中的子路徑也都是最短路徑) ![](https://i.imgur.com/5wxJ6H0.png) - 順帶一提：最長路徑不為Optimal substructure - Negative-weight edge/cycle - 最短路徑的weight可正可負，但不能包含負的cycles(Negative cycles)，因為一直繞會變-∞ ex.下圖的ef和hij，都造成Negative cycles使結果變成-∞ ![](https://i.imgur.com/vebLlEf.png) - Shortest paths are not necessarily unique, and neither are shortest-paths trees Shortest paths可以有多組解，如下圖b和c陰影路徑都呈現了最短路徑的解，都以s為起點但結構不同的shortest-paths trees ![](https://i.imgur.com/BwbUFq0.png) - Relaxation 鬆弛 考慮是否使用u→v這條線edge(u,v)會比較好？ 如果v.d > u.d + w(u,v)，則可以走edge(u,v) 此時紀錄v.d的值為u.d + w(u,v)，v.π = u time complexity= O(1) ![](https://i.imgur.com/7mnqGmD.png)![](https://i.imgur.com/EyXl1BR.png) - Properties of relaxation (不想看就跳過) ![](https://i.imgur.com/K1m2CNN.png) - The Bellman-Ford algorithm 貝爾曼-福特演算法 - Time complexity O(VE) - 權重可以是負的，但不能有負的cycle ![](https://i.imgur.com/EDhFHSr.png) - 參考課本圖解 - 依序對所有edge進行Relax()，只要distance有縮短就替換掉路徑 ![](https://i.imgur.com/b0xlnBI.png) - 或者參考網址：http://alrightchiu.github.io/SecondRound/single-source-shortest-pathbellman-ford-algorithm.html hint： predecessor代表個點的前一個點， distance代表目前為止這個點計算出來的最短路徑距離 一開始所有點的predecessor都設定為-1，所有點的distance都設定為∞ 接著依序對所有edge進行Relax()，只要distance有縮短就替換掉路徑 ![](https://i.imgur.com/nCRm6IV.png) - Single-source shortest paths in directed acyclic graphs(有向無環圖) - Time complexity O(V+E) - 先把topological sort做完，再沿路relax ![](https://i.imgur.com/sksvtbH.png) ![](https://i.imgur.com/PT8uoUF.png) - 補充： 之前說過shortest path是簡單的題目，longest path是難的題目，但是如果是directed acyclic graphs(有向無環圖)，則longest是簡單的題目。 - Dijkstra’s algorithm 戴克斯特拉演算法 - Time complexity O(V^2) (使用BFS方法) ![](https://i.imgur.com/ZFRWNBL.png) - 權重不能有負號 - 模擬BFS方法沿路relax，但途如果有多個點可以走，EXTRACT_MIN(Q)取值最小的點繼續往下走，如圖b(5比10小)，如圖c(7比8和14小)，以此類推，直到所有點都已經塗黑 - EXTRACT_MIN(Q)即是採用Greedy strategy ![](https://i.imgur.com/MHny7mm.png) ![](https://i.imgur.com/FPTNgl5.png) # ch25 All-Pairs Shortest Paths ## 25.1 Shortest paths and matrix multiplication - dynamic-programming algorithm - Initial ![](https://i.imgur.com/OTXu3sV.png) - Then ![](https://i.imgur.com/LVBrzvo.png) - Time Complexity O(n^4) - 改善running time => using repeated squaring (例如W^4 寫成 W^2 * W^2，減少計算次數) => Time Complexity ![](https://i.imgur.com/2ZunHdT.png) ![](https://i.imgur.com/vYZS639.png) ## 25.2 The Floyd-Warshall algorithm - Time complexity O(N^3) - 從vertex(i)走到vertex(j)，逐一引入中繼點vertex(k) ![](https://i.imgur.com/yaJoWqJ.png) ![](https://i.imgur.com/jAlhI7c.png) 為「已將集合K{1,2,3,...k}中的所有vertex作為中繼點引入集合S」後，從起點vertex(i)走到終點vertex(j)的路徑之成本。 ![](https://i.imgur.com/cPkTmrw.png) ![](https://i.imgur.com/NMwhU0G.png) - 參考課本圖解：計算每一個點i到其他點j的距離(ex. 看i=1那行，1到2的距離為3，1到3的距離為8，1到4的距離為∞...) ![](https://i.imgur.com/gTa4bze.png) - 或者參考網址內的圖解：http://alrightchiu.github.io/SecondRound/all-pairs-shortest-pathfloyd-warshall-algorithm.html#floyd - Initial ![](https://i.imgur.com/SqM6wXE.png) - 原本C→B，d=∞。引入A當中繼點，變成C→A→B，d=6 ![](https://i.imgur.com/U5j4MAL.png) - 原本A→C，d=6。引入B當中繼點，變成A→B→C，d=0 - 原本A→D，d=9。引入B當中繼點，變成A→B→D，d=5 ![](https://i.imgur.com/iO5qAM6.png) - 依此類推... ### Transitive closure of a directed graph (傳遞閉包) ![](https://i.imgur.com/X66pTL5.png) ![](https://i.imgur.com/cBugzFm.png) # ch26 Maximum Flow ## 26.1 Flow networks Flow networks and flows ## 26.2 The Ford-Fulkerson method (福特福克森方法) 計算網絡流的最大流的貪心算法。 之所以稱之為「方法」而不是「算法」，是因為它尋找增廣路徑的方式並不是完全確定的，而是有幾種不同時間複雜度的實現方式。 FORD-FULKERSON-METHOD(G,s,t) 三個重要應用： 1. Residual networks (剩餘網路) 2. Augmenting paths 3. Cuts ### Residual networks (剩餘網路) residual capacity (剩餘容量) ### Augmenting paths ### Cuts S在左；T在右，中間切一刀 > Corollary 26.5 > The value of **any flow** f in a flow network G is bounded from above by the capacity of **any cut** of G. > 流量網絡G中任何流量f的值都由G的任意割斷的能力從上方限制。 > Theorem 26.6 (Max-flow min-cut theorem) ### The basic Ford-Fulkerson algorithm FORD-FULKERSON(G,s,t) running time:O(E|f*|) ## 26.3 Maximum bipartite matching 最多的配對 ![](https://i.imgur.com/rIczMPv.png =400x) --- | ch | algorithm | Complexity | | -------- | -------- | -------- | | ch12 | Binary Search Trees | O(h) | | ch13 | Red-Black Trees | O（log n） | | ch18 | B-Trees | O(th)=O(t log~t~n) | | ch19 | Fibonacci Heaps | O(lg n) | | ch21 | Data Structures for Disjoint Sets | O(mα(n)) | | ch22 | Elementary Graph Algorithms | O(V+E) |