11_05_docx

Size: px

Start display at page:

Download "11_05_docx"

叹犁危
4 years ago
Views:

1 圖論 Graph Algorithm 圖是由點 (Node) 與邊 (Edge) 所組成我們可以針對其特性作一些分析以得到我們需要的資料對於一些問題, 也可以將其轉化成一個圖來處理淺談圖形 Graph (1) Graph 的基本定義 : 頂點 (Vertex,V): 在圖形中的點邊弧 (Edge Arc,E,A): 在圖形中連接兩點的連線, 若無向稱為邊 (Edge), 有向則稱為弧 (Arc) 方向性 (Directed): 邊有分有向 (Directed) 與無向 (Undirected) 有向無向混合圖 : 若邊皆為有向邊則稱圖為有向圖皆為無向為無向圖兩者都有則稱混和圖 (2) Graph 的其他定義 i. 分支度 (Degree): 在圖上與頂點相連的邊數為分支度, 若為有向圖則分入 / 出分支度 (in/out-degree) ii. iii. iv. 子圖 (Subgraph): 將原圖形取一些點與邊出來, 即稱其為原圖的子圖權重 (Cost): 在邊上可能路徑 (Path): 由點 A 到點 B 之間所經過的點與邊構成的集合 v. 路徑長度 (Path Length): 路徑上所經過邊數 ( 或權重和 ) vi. vii. viii. ix. 迴路 (Cycle): 如果有一條路徑可使一個點回到自己, 則稱此圖有迴路連通圖 (Connected Graph): 每對點之間都存在一條路徑可以相通通常用於無向圖完全圖 (Complete Graph): 任兩個點之間都有邊相連的圖無圈圖 (Acyclic Graph): 沒有 cycle 的圖 x. 簡單圖 : 不存在連接同一個點的邊, 且任兩點之間最多只有一條邊 xi. 有向無環圖 DAG(Directed Acyclic Graph) 圖的資料結構 Data Structure For Graph (1) 相鄰串列 Adjacency List O(E): 對於每個點紀錄與其相連的點 (2) 相鄰矩陣 Adjacency Matrix O(V 2 ): 以一個二維矩陣 ADJ[u][v], 紀錄點 u 連到點 v 兩者各有優缺點, 使用相鄰矩陣可以迅速知道兩者之間有無邊, 而相鄰串列則在圖較為稀疏的時候搜尋速度會快非常多但相鄰矩陣在稀疏圖的情況下又太浪費空間, 而相鄰串列在查詢時又比較慢 (3) 邊列表 Edge List O(E): 將每條邊的兩個點記錄為一個物件, 視情況採用圖的搜尋法 Searching Method For Graph 圖的搜尋又稱為走訪, 通常採用盲目搜尋 (Blind Searching) 的方法來實踐, 與普通的盲目搜尋類似, 只是將狀態擴展改為點的擴展 ( 亦可將狀態擴展轉化成圖 ), 並加入判斷是否重複走訪常用盲目搜索方法 :DFS BFS DFS-ID DFS (Visited, v) // 開始時 Visited[1~n] 皆為 0 1 Visited[v] 1 2 for u all vertices adjacent to v 3 do if Visited[u] = 0 4 do DFS(Visited, u) BFS (Visited, s) 1 for i 1 to n 2 do Visited[i] 0 3 Initialize Queue 4 Push(s) 5 Visited[s] 1 6 while Queue is not empty 7 do v Pop() 8 for u all vertices adjacent to v 9 do if Visited[u] = 0 10 do Push(u) 11 Visited[u] 1

2 時間戳記 Time-Stamp 在以 DFS 遍歷整個圖時, 記錄進入以及離開節點 (DFS 函數 ) 的時間點 ( 可以視為從編號 1 到邊號 2n 的事件 ), 而這個記錄下來的事件順序則可以幫助我們解決一些問題拓樸排序 Topological Sort 拓樸排序是一種對圖排序的方式, 但是針對什麼作排序呢? 在圖論裡, 拓樸排序可以對一個 DAG 的點進行排序動作, 使得當 u 可以到達 v 時,u 一定排在 v 前面 ( 不是唯一解 ) 利用 Time-Stamp 進行 Topological Sort 以 DFS 遍歷所有點, 並對每個節點訪問完成訪問完成時間時間作 Time-Stamp, 最後將標號順序反過來標號順序反過來即為所求 TOPOLOGICAL SORT() 1 t 0 2 for i 1 to n 3 do Visited[i] 0 4 for i 1 to n 5 do if Visited[i] = 0 6 do DFS (i) DFS(v) 1 Visited[v] 1 2 for u all vertices adjacent to v 3 do if Visited[u] = 0 4 do DFS (u) 5 t t +1 6 f[t]=v; ACM Ordering Tasks John 有 n 件事情要做, 不幸的是這些事情並不是各自獨立的, 而是有相依性的換句話說可能有某件事情一定要在另一件事情做完之後才能做 TIOJ1092 跳格子遊戲 (NPSC2006 初賽 ) 給你一個沒有迴圈的有向圖 Directed Acyclic Graph, 兩位玩家輪流由起點各走一步, 走到終點的人贏如果兩人每一步都是選擇對自己最有利的路徑, 請問你最後是誰獲勝? 強連通元件 Strongly Connected Components(SCC) SCC 的定義 Definition of Strongly Connected Components 在一個有向圖 G 中, 我們可以把 G 的點集 V 分成若干元件, 每個元件中的點滿足這元件中任兩個點都可以互相到達, 且這個元件是 maximal 的 ( 加入任何別的點都沒辦法維持 SCC 的性質 ) 利用 Kosaraju 算法求出 Maximal SCC 用 DFS 走訪方式遍歷原圖, 並且對每個節點訪問完成時間每個節點訪問完成時間作 Time-Stamp, 再按照 Time-Stamp 的先後順序, 由後往前, 在原圖的反向圖原圖的反向圖中作連通塊, 每次得到的連通塊即為一個強連通元件 STRONGLY-CONNECTED-COMPONENT(G) 1 t 0 2 for i 1 to n 3 do Visited[i] 0 4 for i 1 to n 5 do if Visited[i] = 0 6 do DFS (i) 7 for i 1 to n 8 do Visited[i] 0 9 for i n to 1 10 do if Visited[f[i]] = 0 11 do KOSARAJU (f[i]) DFS(v) 1 Visited[v] 1 2 for u all vertices adjacent to v in G 3 do if Visited[u] = 0 4 do DFS (u) 5 t t +1 KOSARAJU(v) 6 f[v]= t; 1 Add v to Scc 2 Visited[v] 1 3 for u all vertices adjacent to v in G T 4 do if Visited[u] = 0 5 do KOSARAJU (u)

3 SCC 的用途 SCC 一般的用途是可以幫助我們進行縮點的動作, 可以將一般圖化為 DAG, 方便我們利用其性質不過當然 SCC 本身的一些特性也常常被用來解決問題 USACO CONTEST 2003 NOVEMBER GREEN - Popular Cows(popular) 每一頭牛的願望就是變成一頭最受歡迎的牛現在有 N 頭牛, 給你 M 對整數 (A,B), 表示牛 A 認為牛 B 受歡迎這種關係是具有傳遞性的, 如果 A 認為 B 受歡迎,B 認為 C 受歡迎, 那麼牛 A 也認為牛 C 受歡迎你的任務是求出有多少頭牛被所有的牛認為是受歡迎的 USACO TRAINING CHAP 5.3 Network of Schools (schlnet) 一些學校連入一個電腦網絡每個學校都會給其它的一些學校分發軟體 ( 稱作接受學校 ) 注意如果 B 在 A 學校的分發列表中, 那麼 A 不一定也在 B 學校的列表中你要寫一個程式計算, 為了讓網絡中所有的學校都用上新軟體, 必須接受新軟體副本的最少學校數目 ( 子任務 A) 更進一步, 我們想要確定通過給任意一個學校發送新軟體, 這個軟體就會分發到網絡中的所有學校為了完成這個任務, 我們可能必須擴展接收學校列表, 使其加入新成員計算最少需要增加幾個擴展, 使得不論我們給哪個學校發送新軟體, 它都會到達其餘所有的學校 ( 子任務 B) 一個擴展就是在一個學校的接收學校列表中引入一個新成員雙連通元件 BiConnected Components(BCC) BCC 的定義 Definition of BiConnected Components 在一個連通無向圖 G 中, 我們可以把 G 的邊集 E 分成若干元件, 每個元件中, 滿足任兩條邊都同時在某個圈上 ( 或任兩點之間路徑不只一條 ), 且這個元件是 maximal( 加入任何別的邊都沒辦法維持 BCC 性質 ) 利用 Dfn() 與 Low() 求出 Maximal BCC (By John Hopcroft and Robert Tarjan) 對 G 作 DFS, 定義 Dfn[v] 為點 v 的先深序號, 並定義 Low[v] = Min(Dfn[v], Low[u], Dfn[w]) u 為 v 在 DFS Tree 上的一個子節點,(v, w) 為一在 DFS Tree 上的 Back edge 在 DFS 過程中, 我們維持一個 stack 來存放目前走過的邊, 在過程中, 當一個點 DFS 結束後, 若其 Low[v] Dfn[v], 則代表自己以及位置在其以上的所有邊為一 BCC BICONNECTED-COMPONENT (G) 1 t 0 2 top 0 3 for i 1 to n 4 do Dfn[i] 0 5 DFS (1,1) DFS(p,v) 1 t t + 1 Dfn[v] t 2 Low[v] Dfn[v] 3 for u all vertices adjacent to v in G 4 do if Dfn[u] < Dfn[v] 5 do stack[top] (v,u), top top do if Dfn[u] = 0 7 DFS (v,u) 8 Low[v] Min ( Low[v], Low[u] ) 9 do else if u p 10 do Low[v] Min ( Low[v], Dfn[u] ) 11 do if Low[v] Dfn[v] 12 do Pop stack into a BCC until{pop = (p,v)}

4 BCC 的用途 BCC 可以將原本的圖 G 縮成新的圖 G, 在 G 中不存在任何 cycle 這樣的性質有時候可以幫助我們解決問題除此之外, 我們可以利用求 BCC 的方法, 找出一個圖 G 中的 Bridge( 若拿掉此邊,G 會變成不連通的 ) 和 Articulation Point( 若拿掉此點,G 不連通 ) TIOJ 1137 收費站設置問題蕃茄國有 n 個城市以及 m 條雙向道路連接這 n 個城市, 並且任何兩個城市之間都至少有一條路可以到達由於國家財政上的困難, 蕃茄國的行政部門想要在這些城市當中選一些城市設置收費站, 而這些被選中的城市滿足 : 至少有除了被選中城市以外的兩個城市, 其所有連接該二城市的路徑都必須經過被選中的城市現在給你蕃茄國的地圖, 請問有多少個城市可以設置收費站呢? 挑戰題 PKUOJ Knights of the Round Table 給出一些騎士直接的關係, 要從這些騎士中選出奇數位坐到一個圓桌, 相互憎恨的騎士不能坐在相鄰位置問有哪些騎士永遠不可能做到圓桌上最小生成樹 Minimum Spanning Tree (MST) MST 的定義 Definition of Minimum Spanning Tree 給定一個圖 G, 其每條邊被賦予了一個權重, 從其邊集 E 中選擇其中的一些邊, 使得這些邊能夠連接所有的點, 而且權重總和是最少的且因為形成 Cycle 必可消去某邊且保持 MST 特性, 又必須保持連通狀態, 可知 MST 必為一 Tree MST 的貪心性質在一個無向圖 G=(V,E) 中, 令 U 為一個頂點集 V 的子集, 在所有一端屬於 U, 一端屬於 V - U 的邊長集中, 最小的一段必為 MST 的一邊首先假設所有的 MST 都不包含該邊, 所以加入其後必形成的迴圈由於其為最小的一段邊, 迴圈中必有比其大的邊, 消掉後反而可以形成更小的 MST, 反證法得證利用 Prim s Algorithm 求出 MST - O(m lgn) 核心思想 : 由任一個點開始擴展 MST, 每次選擇目前加進來所需 cost 最小的點把它加入, 並更新到每個點所需要增加的 cost 值用 heap 來 implement 虛擬碼 MST-Prim, 回傳 MST 的 cost MST-PRIM () 1 totalcost 0 2 for each u V 3 do u.cost 4 r.cost 0 // r is any node in V 5 make V into a min-heap Heap determined by the value of cost 6 while Heap is not empty 7 do u EXTRACT-MIN (Heap) 8 totalcost totalcost + u.cost 9 for each vertex v Adj[u] 10 do if v Heap and w(u, v) < v.cost // where w(u, v) is the weight of edge (u, v) 11 then v.cost w(u, v) 12 return totalcost

5 利用 Kruskal s Algorithm 求出 MST - O(m lg n) 核心思想 : 每次挑選 cost 最小且其兩端點尚未相連的邊加入 MST, 用 Disjoint Set 來 implement 虛擬碼 : MST-Kruskal, 回傳 MST 的 cost MST-KRUSKAL () 1 totalcost 0 2 for each v V 3 do MAKE-SET (v) 4 sort the edges into non-decreasing order by weight 5 for each edge (u, v) E, taken in non-decreasing order 6 do if FIND-SET (u) FIND-SET (v) 7 then UNION (u, v) 8 totalcost totalcost + w(u, v) 9 return totalcost TIOJ 1211 圖論之最小生成樹給你一個加權的無向圖 (weighted undirected graph), 請問這個圖的最小生成樹 (minimum spanning tree) 的權重和為多少? TIOJ 1445/ACM 機器人組裝大賽 /ACM Contest and Blackout 給你一個加權的無向圖 (weighted undirected graph), 請問這個圖的次小生成樹 (minimum spanning tree) 的權重和為多少? 最短路徑 Shortest Path (SP) 最短路徑問題是圖論中的一個經典問題, 主要在尋找兩節點之間的最短路徑, 又依範圍兩類演算法 : 單源最短路徑 (Single Source Shortest Path,SSSP) 所有點對最短路徑(All Pairs Shortest Path,ASAP) 為求簡便表達虛擬碼, 首先定義一個鬆弛 (Relax) 函式以及 SSSP 的初始化函式 RELAX (u, v) 1 if d[v] > d[u] + w(u, v) 2 then d[v] d[u] + w(u, v) 3 π[v] u 單源最短路徑 Single Source Shortest Path(SSSP) INITIALIZE-SINGLE-SOURCE (S) 1 for each vertex v V 2 do d[v] 3 π[v] NIL 4 d[s] 0 1. Dijkstra s SSSP Algorithm( O(n 2 ) / O(n + m lg n) ) Dijkstra 算 SSSP 演算法中較快速的一個, 但其只適用於沒有負邊 (negative edge) 的圖核心思想 : 與 Prim s 演算法相似的,Dijkstra 每次 Greedy 地抓出目前距離最短且沒有擴展過的點作擴展, 對於該點與其邊作鬆弛動作, 直至無法抓出點為止 (n-1 次 ) 在稀疏圖使用 Heap 可加速許多, 但若邊遠大於點數, 反而會比枚舉點更慢, 應當慎選 DIJKSTRA (S) 1 INITIALIZE-SINGLE-SOURCE (S) 2 Heap V 3 while Heap Ø 4 do u EXTRACT-MIN (Heap) 5 for each vertex v Adj[u] 6 do RELAX (u, v)

6 2. Bellman-Ford SSSP Algorithm( O(V E) ) Bellman-Ford 雖然較慢 ( 但稀疏圖很快 ), 但可以處理有負邊的情況, 更可以判斷是否存在負圈核心思想 : 連續 V - 1 次對每條邊進行鬆弛動作, 若最後仍能鬆弛, 則存在負圈加速法 : 當有一輪發現無法鬆馳時, 即可跳出迴圈, 因之後必無法再行鬆弛 BELLMAN-FORD (S) 1 INITIALIZE-SINGLE-SOURCE (S) 2 for i 1 to V do for each edge (u, v) E 4 do RELAX (u, v) 5 for each edge (u, v) E 6 do if d[v] > d[u] + w(u, v) 7 then return FALSE 8 return TRUE 3. Shortest Path Faster Algorithm,SPFA (SSSP)( O(k E) ) SPFA 是 Bellman-Ford 的一種佇列表示形態, 可以省去一些沒必要的計算, 也可以計算負邊的情況 ( 但不可存在負圈 ), 且寫起來比其他方法較為方便核心思想 : 將源點加入佇列中, 在重複對於佇列的元素連接的邊作鬆弛, 若鬆弛成功且該點未在佇列中, 則將其加入佇列, 直至佇列為空為止 SPFA (S) 1 INITIALIZE-SINGLE-SOURCE (S) 2 for i 1 to n 3 do aug[i]=0 4 Enqueue(S) 5 while not (Empty) do 6 u Dequeue() 7 aug[u] 0 8 do for each edge (u, v) E 9 do if RELAX (u, v) and aug[v] = 0 10 Enqueue(v) 11 aug[u] 1 4. Floyd-Warshall APSP Algorithm( O(n 3 ) ) Floyd-Warshall 是一種十分容易撰寫的 APSP 演算法, 可以處理一般圖 ( 包括負邊 ) 的最短路徑問題核心思想 : 原理是動態規劃,Dist[i][j][k]=Min(Dist[i][k][k-1]+Dist[k][j][k-1],Dist[i][j][k-1]), 但在實際撰寫的過程中, 可以直接將三維的空間壓縮, 額外再加上一層迭代以節省空間 FLOYD-WARSHALL () 1 Initiailize D with the Distance Matrix of graph G 2 for k 1 to n 3 do for i 1 to n 4 do for j 1 to n 5 do D ij min(d ij, D ik +D kj )

7 5. Johnson s APSP Algorithm( O(n 2 lg m + n m) ) Johnson 算是一種加強版的 Dijkstra, 為了無法處理負邊的問題,Johnson 首先使用一次 Bellman-Ford 對於所有點重新標號 ( 賦予每個點一個權重 h(x) ), 並將邊更換成非負邊 ( w (u,v) = w(u,v)+h(u)-h(j)), 再對每個點作 Dijkstra, 在圖偏稀疏的時候比 Floyd-Warshall 快 TIOJ 1290 不定向邊給一個圖, 單向邊, 邊有 cost, 一開始邊是未決定方向的, 你可以對任意條邊決定一個方向接著, 問起點到終點最短路徑 ACM Sending Mail 給有 N 個點,M 條邊 ( 雙向 ) 的圖, 邊上有權重, 問從點 S 走到點 T 的最小成本是多少? ACM Asterix and Obelix 地圖上有一些城市 (<80), 現在有兩個人 A 跟 B 分別在兩地, 他們要回到城 X 的家去, 然而走過兩個城市之間的道路需要過路費, 而且 B 要求 A 要請客, 請客的地點是在選在某個城市, 在每個城市請客的價錢不一樣, 然後 B 要求 A 請客的地點必需是 A 回家的路上 ( 含 A 和 X) 最貴的那一個城市, 也就是說 A 回家的花費是路徑上過路費的總和, 再加上路上最貴城市的價錢現在給你一張地圖, 以及 A 所在的城市編號 X 城的編號 ( 會問很多次 ), 請計算 A 回家所需的最小花費是多少 ( 對每一次問題分別輸出答案 )? ACM558 Wormholes 公元 2163 年, 科學家們發明了蟲洞, 一個蟲洞的兩端可以連接兩個地點, 之間可能有時間差你想知道可不可能利用這些蟲洞, 來做時光旅行, 所謂時光旅行是必須到達同一地點的較早時間, 給你 N 1000 個地點和 M 2000 個蟲洞, 接下來 M 個蟲洞用 a b c 表示 : 從 a 到 b( 單向的 ), 時間會增加 c 年 ( 負值表示倒退 ), 問時光旅行有沒有可能實現? ACM Rendezvous 我們的小組想在一個地方集合並且作功課我們這個 05-2 小組有 22 個組員因為我們有點疑惑哪裡是跟大家見面的最好地方所以我們決定在一個可以讓總耗費的量最少的地方見面總耗費量的定義是從所有人到目的地的總距離在本題中, 你被要求寫一個程式來找出有機會能夠有最少耗費量的地點, 而每個組員的家就是那些可能的地點 USACO TRAINING CHAP2.3 Bessie Come Home(comehome) 現在是晚餐時間, 而母牛們在外面分散的牧場中 FJ 按響了電鈴, 所以她們開始向穀倉走去你的工作是要指出哪只母牛會最先到達穀倉 ( 在給出的測試數據中, 總會有且只有一隻速度最快的母牛 ) 在擠奶的時候 ( 晚餐前 ), 每隻母牛都在她自己的牧場上, 一些牧場上可能沒有母牛每個牧場由一條條道路和一個或多個牧場連接 ( 可能包括自己 ) 有時, 兩個牧場 ( 可能是自我相同的 ) 之間會有超過一條道路相連至少有一個牧場和穀倉之間有道路連接因此, 所有的母牛最後都能到達穀倉, 並且母牛總是走最短的路徑當然, 母牛能向著任意一方向前進, 並且她們以相同的速度前進牧場被標記為 'a'..'z' 和 'A'..'Y', 在用大寫字母表示的牧場中有一隻母牛, 小寫字母中則沒有穀倉的標記是 'Z', 注意沒有母牛在穀倉中注意 'm' 和 'M' 不是一個牧場想一想如果要求的是第 k 短路, 有沒有什麼好方法呢?

全唐诗28

全唐诗28 ... 1... 1... 1... 2... 2... 2... 3... 3... 4... 4... 4... 5... 5... 5... 5... 6... 6... 6... 6... 7... 7... 7... 7... 8... 8 I II... 8... 9... 9... 9...10...10...10...11...11...11...11...12...12...12...13...13...13...14...14...14...15...15...15...16...16...16...17...17