演算法 期末考 筆記

課本習題的解答多看有益身心健康

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
    

• TREE_SEARCH(x, k)

  • O(h)

• ITERATIVE_SEARCH(x, k)

  • 例題12.2-1 哪個組合不可能是BST search 363的過程？
    
  • 參考答案：c、e是錯的
    
  • 例題12.2-4 Professor Bunyan發現一個屬性
    search path左邊的所有節點a < search path上的所有的節點b < search path右邊的所有節點c
    解釋是否正確？
    
  • 參考答案：不正確 (以下範例假設要search key 4)
    

• 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)
     

  2. 如果x.right是null，往上找x的祖先y，直到找到第一個y的左子樹是x的祖先 (ex.13的successor為15)
     

  • The dynamic-set operations：O(h)(tree of height h)
  • 例題12.2-5 證明一個node有兩個小孩，則他的successor沒有左邊小孩，他的predecessor沒有右邊小孩
    
  • 參考解答：
    假設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
3. 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)
   

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.以某個節點為起點，往下到所有葉子的的路徑上的黑點數量相同
    
  • 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.
  • 可能會考如何畫rotation前後如何畫圖(ex.如下圖)
    

• 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)
    
    • 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的位置變化比較好理解
      
  • 例題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.
  • 參考答案：
    

• 13.4 Deletion

  • O(lg n)
  • RB-DELETE(T,z)
    • 如果被刪除的節點是紅色 => RB tree的平衡還在
    • 如果被刪除的節點是黑色 =>會違反RB Tree的原則，要執行RB-DELETE-FIXUP
  • RB-DELETE-FIXUP(T, x)
    
    
    -如果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的位置變化比較好理解
      
      
      
  • 例題13.4-3 依照13.3-2的結果依序刪除8; 12; 19; 31; 38; 41.
  • 參考答案：
    

ch18 B-Trees

• 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)。
    
    

• Search

  • Run Time
    
  • 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
    
  • 從root沿路scan，只要遇到full就先split
  • t=3為例，Insert B、Q、L、F
    
    

• Delete　（從上往下跑，遇到不足的就合起來）（不足：t-1）

  • Run Time

    

  • 從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
    

    
    
    

ch19 Fibonacci Heaps

• Structure of Fibonacci heaps
  

  
  • 上層為root list，root list最小的點為H.min
  • 曾經失去一個小孩就會變成黑色(H.mark=true)
  • 變成別人小孩就會變成白色(H.mark=false)

• Potential function

  • = 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的範例
    
    

• 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
    
    
    
    

• 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
    
    

• 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
    
    
  • 參考答案：
    
    

• 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)。
      
      
      
      
  • A weighted-union heuristic(考慮每個set的長度，短的併到長的)
    • 每一個representative存放其代表的序列的長度。
    • 把較短的序列附加在較長的序列之後。(可以節省union時間)

• Disjoint-set forests (rooted tree)

  • Tree的root為代表人(representative)。
    
    
  • 改善running time的方法：
    • Union by rank: 由較小高度的的tree的root連到較大的tree的root。
    • Path compression: 在執行Find-Set(x)過程中，把所有經過的node都掛在root底下。 (壓縮)
      
      

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)]

• 無方向：矩陣&串列表示法
  
  
• 有方向：矩陣&串列表示法
  
  

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點相鄰的點集合

• 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標記為黑色視為以搜尋完成所有相鄰的點

參考網址：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點相鄰的點集合

• line:1-3，loop所有點初始化
• line:4，time初值
• line:5-7，loop所有點u，判斷白色(未拜訪過)的點後執行[DFS-VIST(G,u) Recursion]recurse

• 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©：不同component的edge。
• 

參考網址：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可能不止一種

• 透過DFS(G)計算各節點完成時間(標記黑色的順序)
• 將各節點完成時間由大到小排序

• 做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)

• 透過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)

• 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：沒有循環且連結所有點
  
  

23.1 Growing a minimum spanning tree

• 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

• line:1-3，初始化
• line:4，把圖的所有邊(edges)以權重(weight)由小到大做排序
• line:5-8，loop所有邊(edges)依權重由小到大運行，判斷邊 u 和 v 在不同集合中，便將邊(u,v)放入A集合中，u 和 v 的點集合聯集
  
  
  
  

參考網址：Minimum Spanning Tree：Kruskal's Algorithm
http://alrightchiu.github.io/SecondRound/minimum-spanning-treekruskals-algorithm.html

Prim’s algorithm

• 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 之間的權重找最小者
  
  

參考網址：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
  

  

• 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(最短路徑中的子路徑也都是最短路徑)
    

    

  • 順帶一提：最長路徑不為Optimal substructure

• Negative-weight edge/cycle

  • 最短路徑的weight可正可負，但不能包含負的cycles(Negative cycles)，因為一直繞會變-∞
    ex.下圖的ef和hij，都造成Negative cycles使結果變成-∞
    
    

• Shortest paths are not necessarily unique, and neither are shortest-paths trees
  Shortest paths可以有多組解，如下圖b和c陰影路徑都呈現了最短路徑的解，都以s為起點但結構不同的shortest-paths trees
  

  

• 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)
  

  
  
  • Properties of relaxation (不想看就跳過)
    
    

• The Bellman-Ford algorithm 貝爾曼-福特演算法

  • Time complexity O(VE)

  • 權重可以是負的，但不能有負的cycle
    

    

  • 參考課本圖解

    • 依序對所有edge進行Relax()，只要distance有縮短就替換掉路徑
      
      

  • 或者參考網址：http://alrightchiu.github.io/SecondRound/single-source-shortest-pathbellman-ford-algorithm.html
    hint：
    predecessor代表個點的前一個點，
    distance代表目前為止這個點計算出來的最短路徑距離
    一開始所有點的predecessor都設定為-1，所有點的distance都設定為∞
    接著依序對所有edge進行Relax()，只要distance有縮短就替換掉路徑
    

    

• Single-source shortest paths in directed acyclic graphs(有向無環圖)

  • Time complexity O(V+E)
  • 先把topological sort做完，再沿路relax
    
    
    
    
  • 補充：
    之前說過shortest path是簡單的題目，longest path是難的題目，但是如果是directed acyclic graphs(有向無環圖)，則longest是簡單的題目。

• Dijkstra’s algorithm 戴克斯特拉演算法

  • Time complexity O(V^2) (使用BFS方法)
    

    

  • 權重不能有負號

  • 模擬BFS方法沿路relax，但途如果有多個點可以走，EXTRACT_MIN(Q)取值最小的點繼續往下走，如圖b(5比10小)，如圖c(7比8和14小)，以此類推，直到所有點都已經塗黑

  • EXTRACT_MIN(Q)即是採用Greedy strategy
    

    
    
    

ch25 All-Pairs Shortest Paths

25.1 Shortest paths and matrix multiplication

• dynamic-programming algorithm

  • Initial
    
    
  • Then
    
    
  • Time Complexity O(n^4)
  • 改善running time => using repeated squaring (例如W^4 寫成 W^2 * W^2，減少計算次數) => Time Complexity
    
  

25.2 The Floyd-Warshall algorithm

• Time complexity O(N^3)

• 從vertex(i)走到vertex(j)，逐一引入中繼點vertex(k)
  

  
  
  為「已將集合K{1,2,3,…k}中的所有vertex作為中繼點引入集合S」後，從起點vertex(i)走到終點vertex(j)的路徑之成本。
  
  
  
  

• 參考課本圖解：計算每一個點i到其他點j的距離(ex. 看i=1那行，1到2的距離為3，1到3的距離為8，1到4的距離為∞…)
  

  

• 或者參考網址內的圖解：http://alrightchiu.github.io/SecondRound/all-pairs-shortest-pathfloyd-warshall-algorithm.html#floyd

  • Initial
    
    
  • 原本C→B，d=∞。引入A當中繼點，變成C→A→B，d=6
    
    
  • 原本A→C，d=6。引入B當中繼點，變成A→B→C，d=0
  • 原本A→D，d=9。引入B當中繼點，變成A→B→D，d=5
    
    
  • 依此類推…

Transitive closure of a directed graph (傳遞閉包)

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

最多的配對

---

ch	algorithm	Complexity
ch12	Binary Search Trees	O(h)
ch13	Red-Black Trees	O（log n）
ch18	B-Trees	O(th)=O(t logtn)
ch19	Fibonacci Heaps	O(lg n)
ch21	Data Structures for Disjoint Sets	O(mα(n))
ch22	Elementary Graph Algorithms	O(V+E)