# 1092 Algorithm Ex5 ###### tags: `courses`, `assignment` ## Algo design 因為懶的自己寫 linked-list 便使用 C++ 的 `vector` ### data structure 使用 adjacent list. >問題： 在計算 residual graph 時需要同時用到 uv 與 vu 從 uv 得到 vu 需要最多 E 的時間 因此我增加 `invertIndex` 在 edge 裡面，紀錄與自己成對的那個邊的 index (由於我用 `vector` 不是 linked-list 因此使用 index 而不是 pointer，若使用 pointer 會出問題，因為 `vector` 在 `push_back` 時有機會從新 allocate memory) 有了 `invertIndex` 便可以以 $O(1)$ 的時間查找到與自己向對應的 edge ```graphviz digraph { rankdir=LR; 0 -> 1 [dir="none"] 0 -> 2 [dir="none"] 1 -> 3 [dir="none"] 2 -> 3 [dir="none"] } ``` ```graphviz digraph { node [shape="record"] rankdir=LR; arr [label="<0>\n0\n|<1>\n1\n|<2>\n2\n|<3>\n3\n\n"] a0 [label="{1|2}"] a1 [label="{0|3}"] a2 [label="{0|3}"] a3 [label="{1|2}"] arr:0->a0 arr:1->a1 arr:2->a2 arr:3->a3 label="普通的 adjacent list" } ``` ```python= g[3][0].to == 1 # 得知 edge(3,1) 存在 for i := 0 ~ g[1].size if g[1][i] == 3 # g[1][i] 為 edge(1,3) # 結論需要迭代整個 g[1] 陣列去尋找 edge(1,3) ``` ```graphviz digraph { node [shape="record"] rankdir=LR; arr [label="<0>\n0\n|<1>\n1\n|<2>\n2\n|<3>\n3\n\n"] a0 [label="{1 (0)|2 (0)}"] a1 [label="{0 (0)|3 (0)}"] a2 [label="{0 (1)|3 (1)}"] a3 [label="{1 (1)|2 (1)}"] arr:0->a0 arr:1->a1 arr:2->a2 arr:3->a3 label="紀錄 invert index" } ``` ```python= g[3][0].to == 1 # 得知 edge(3,1) 存在 invertIndex = g[3][0].invertIndex g[1][invertIndex] == 3 # 找到 edge(1,3) ``` ### 演算法 #### 找 global min-cut 使用 Ford Fulkerson，用 dfs 尋找 arumenting path。 固定一點 u 對其他所有 v 做一次 FordFulkerson(u, v)，找出最小的 min-cut 最小的 min-cut 便是 global min-cut #### 找 min-cut edge 假設目前的 residual graph (簡稱 $G_r$) 就是 global min-cut 的 $G_r$ 那麼用做到最後的 $G_r$ 從 src 開始進行一次 DFS，會得知一些 vertex 為 reachable 一些為 unreachable，而在 reachable vertex 與 unreachable vertex 之間的 edge 及為 min-cut edge 可以理解成從 src 開始往 sink 那半邊，走到走不過去時，那些擋住你的 edge 就是導致塞車的關鍵點。 ### pseudo code ```python= FordFulkerson(rG, src, sink): mincut := 0 visited := [0, 0, ...] while true if dgsArgPath(rG, visited, src, sink) == true: mincut += 1 # 每次必定只會增加ㄧ else: break return mincut dfsArgPath(rG, visited, v, sink): for i := 0 ~ rG[v].size if rG[v][i].residual > 0: if rG[v][i].to == sink: foundPath = true else if visited[rG[v][i].to] == false visited[rG[v][i].to] = true dfsArgPath(rG, visited, rG[v][i].to, sink) if foundPath: rG[v][i].residual -= 1 rG[v][i].invertEdge.residual += 1 # 更新 residual graph return true findMinCutEdge(G, rG, src, sink): visited = [0, 0...] ans = [] ForFulkerson(rG, src, sink) # 做一次 fordfulkerson 以獲得 residual graph dfs(rG, visited, src) for i := 0 ~ |V| # for each vertex if visited[i] for j := 0 ~ G[i].size # for each edge connected to this vertex if visited[G[i][j].to] == false # vectex i is reachable and vertex G[i][j].to is unreachable ans.add(edge(i, G[i][j].to)) return ans main(G): src = 0 rG = transform(G) # 將無向圖 G 換成雙向， capicity 為 1 得 residual graph for sink := 1 ~ |V| reset rG if globalMincut > Fordfulkerson(rG, src, sink): globalMincut = Fordfulkerson(rG, src, sink) finalSink = sink mincutEdge = findMinCutEdge(G, rG, src, sink) ``` ## Analyze 一次 argumenting path 最糟就是把每一邊都走過：$O(E)$ 一次 argumenting path 可以增加 1 flow. 在無向無權重圖中，flow 最多等於 $E$ 因此最多做 $E$ 次 arumenting path 因此 一次 Ford Fulkerson 最糟 $O(E^2)$ 為了找 global min-cut 我們做了 $V$ 次 FordFulkerson: $O(VE^2)$ 找 min-cut edge 需要一次 Ford Fulkerson 並 dfs 一次圖，再測試所有的邊是否是 min-cut edge $O(E^2 + E + E) = O(E^2)$ 整體：$O(VE^2 + E^2) = O(VE^2)$