Kosaraju 的 scc 算法

Question

谁能解释一下 Kosaraju\xe2\x80\x99s 查找连通分量算法背后的逻辑？

\n\n

我已阅读说明，但我无法理解反转图上的 DFS 如何检测强连通分量的数量。

\n\n

def dfs(visited, stack, adj, x):\n    visited[x] = 1\n\n    for neighbor in adj[x]:\n        if (visited[neighbor]==0):\n            dfs(visited, stack, adj, neighbor)\n\n    stack.insert(0, x)\n    return stack, visited\n\ndef reverse_dfs(visited, adj, x, cc):\n    visited[x] = 1\n\n    for neighbor in adj[x]:\n        if (visited[neighbor]==0):\n            cc += 1\n            reverse_dfs(visited, adj, neighbor,cc)\n    print(x)\n    return cc\n\n\ndef reverse_graph(adj):\n    vertex_num = len(adj)\n    new_adj = [ [] for _ in range(vertex_num)]\n    for i in range(vertex_num):\n        for j in adj[i]:\n            new_adj[j].append(i)\n    return new_adj\n\n\ndef find_post_order(adj):\n    vertex_num = len(adj)\n    visited = [0] * vertex_num\n    stack = []\n\n    for vertex in range(vertex_num):\n        if visited[vertex] == 0:\n            stack, visited = dfs(visited, stack, adj, vertex)\n\n    return stack\n\n\ndef number_of_strongly_connected_components(adj):\n    vertex_num = len(adj)\n    new_adj = reverse_graph(adj)\n    stack = find_post_order(adj)\n\n    visited = [0] * vertex_num\n    cc_num = 0\n    while (stack):\n        vertex = stack.pop(0)\n        print(vertex)\n        print(\'------\')\n        if visited[vertex] == 0:\n            cc_num = reverse_dfs(visited, new_adj, vertex, cc_num)\n    return cc_num\n\nif __name__ == \'__main__\':\n    input = sys.stdin.read()\n    data = list(map(int, input.split()))\n    n, m = data[0:2]\n    data = data[2:]\n    edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))\n    adj = [[] for _ in range(n)]\n    for (a, b) in edges:\n        adj[a - 1].append(b - 1)\n    print(number_of_strongly_connected_components(adj))\n

\n\n

在上面你可以找到我的实现。我猜初始 DFS 和反向操作已正确完成，但我不知道如何正确执行第二个 DFS。\n提前致谢。

\n

Answer 1

您应该注意到的第一件事是，对于图及其反面来说，强连通分量的集合是相同的。事实上，该算法实际上是在反转图中找到强连通分量的集合，而不是原始图中（但这没关系，因为两个图都有相同的 SCC）。

第一个 DFS 执行会产生一个堆栈，该堆栈以特定顺序保存顶点，这样当第二个 DFS 按此顺序（在反转图上）对顶点执行时，它就会正确计算 SCC。因此，运行第一个 DFS 的全部目的是找到图顶点的排序，以服务于反转图上的 DFS 算法的执行。现在我将解释堆栈中的顶点顺序具有什么属性以及它如何服务于反转图上的 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 的每个顶点，并且由于从 S2 无法到达 S1 的任何顶点，因此我们在探索 S1 的任何顶点之前先探索 S2 的所有顶点。但这适用于任何一对连接的组件，其中一个组件可以从另一个组件访问。特别是，堆栈顶部的顶点属于接收器组件，并且在我们完成探索该接收器组件之后，顶部顶点再次属于相对于尚未探索的顶点引起的图的接收器。

因此，该算法正确地计算了反转图的所有强连通分量，如上所述，这些强连通分量与原始图中的相同。