亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

scc 的 Kosaraju 算法

scc 的 Kosaraju 算法

UYOU 2021-09-11 14:50:17
任何人都可以向我解釋 Kosaraju 尋找連通分量的算法背后的邏輯嗎?我已閱讀說明,但我無法理解反向圖上的 DFS 如何檢測強連接組件的數量。def dfs(visited, stack, adj, x):    visited[x] = 1    for neighbor in adj[x]:        if (visited[neighbor]==0):            dfs(visited, stack, adj, neighbor)    stack.insert(0, x)    return stack, visiteddef reverse_dfs(visited, adj, x, cc):    visited[x] = 1    for neighbor in adj[x]:        if (visited[neighbor]==0):            cc += 1            reverse_dfs(visited, adj, neighbor,cc)    print(x)    return ccdef reverse_graph(adj):    vertex_num = len(adj)    new_adj = [ [] for _ in range(vertex_num)]    for i in range(vertex_num):        for j in adj[i]:            new_adj[j].append(i)    return new_adjdef find_post_order(adj):    vertex_num = len(adj)    visited = [0] * vertex_num    stack = []    for vertex in range(vertex_num):        if visited[vertex] == 0:            stack, visited = dfs(visited, stack, adj, vertex)    return stackdef number_of_strongly_connected_components(adj):    vertex_num = len(adj)    new_adj = reverse_graph(adj)    stack = find_post_order(adj)    visited = [0] * vertex_num    cc_num = 0    while (stack):        vertex = stack.pop(0)        print(vertex)        print('------')        if visited[vertex] == 0:            cc_num = reverse_dfs(visited, new_adj, vertex, cc_num)    return cc_numif __name__ == '__main__':    input = sys.stdin.read()    data = list(map(int, input.split()))    n, m = data[0:2]    data = data[2:]    edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))    adj = [[] for _ in range(n)]    for (a, b) in edges:        adj[a - 1].append(b - 1)    print(number_of_strongly_connected_components(adj))在上面你可以找到我的實現。我猜初始 DFS 和反向操作已正確完成,但我無法正確執行第二個 DFS。提前致謝。
查看完整描述

1 回答

?
慕妹3146593

TA貢獻1820條經驗 獲得超9個贊

您應該注意到的第一件事是,圖及其反向的強連通分量集是相同的。實際上,該算法實際上是在反轉圖中找到了一組強連通分量,而不是原始圖(但沒關系,因為兩個圖具有相同的 SCC)。

第一次 DFS 執行會產生一個以特定順序保存頂點的堆棧,這樣當第二個 DFS 以該順序(在反轉圖上)在頂點上執行時,它就會正確計算 SCC。因此,運行第一個 DFS 的全部目的是找到圖頂點的排序,該排序服務于在反向圖上執行 DFS 算法?,F在我將解釋堆棧中頂點順序的屬性是什么,以及它如何在反轉圖上執行 DFS。

那么棧的屬性是什么?想象 S1 和 S2 是圖中的兩個強連通分量,在逆向圖中,S2 可以從 S1 到達。顯然,S1 也無法從 S2 到達,因為如果是這種情況,S1 和 S2 將合并為一個組件。設 x 是 S1 中頂點中的頂部頂點(即,S1 中的所有其他頂點在堆棧中都低于 x)。類似地,讓 y 成為 S2 中頂點中的頂部頂點(同樣,S2 中的所有其他頂點在堆棧中都低于 y)。屬性是y(屬于S2)在堆棧中高于x(屬于S1)。

為什么這個屬性有幫助?當我們在逆向圖上執行DFS時,我們是按照堆棧順序來做的。特別是,我們在探索 x 之前探索 y。在探索 y 時,我們探索 S2 的每個頂點,由于 S1 的任何頂點都不能從 S2 到達,所以我們在探索 S1 的任何頂點之前探索 S2 的所有頂點。但這適用于任何一對連接的組件,這樣一個組件可以從另一個組件到達。特別是,堆棧頂部的頂點屬于匯組件,在我們完成對匯組件的探索之后,相對于尚未探索的頂點所誘導的圖,頂部頂點再次屬于匯。

因此,該算法正確地計算了逆向圖中的所有強連通分量,如前所述,它們與原始圖中的相同。


查看完整回答
反對 回復 2021-09-11
  • 1 回答
  • 0 關注
  • 147 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號