- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
谁能给我解释一下 Kosaraju 寻找连通分量的算法背后的逻辑?
我已阅读 description ,尽管我不明白反转图上的 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, visited
def 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 cc
def 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_adj
def 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 stack
def 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_num
if __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。提前致谢。
最佳答案
您应该注意的第一件事是,对于图及其逆向,强连通分量集是相同的。事实上,该算法实际上是在反转图中找到强连通分量集,而不是原始图(但这没关系,因为两个图具有相同的 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 的每个顶点,并且由于 S1 的顶点无法从 S2 到达,因此我们在探索 S1 的任何顶点之前探索 S2 的所有顶点。但这适用于任何一对连接的组件,这样一个组件就可以从另一个组件到达。特别是,堆栈顶部的顶点属于一个汇组件,在我们完成对汇组件的探索后,顶部顶点再次属于一个汇,相对于由尚未探索的顶点导出的图。
因此,该算法正确计算了反转图的所有强连通分量,如前所述,这些分量与原始图中的相同。
关于python - Kosaraju 的 scc 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53680188/
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 8 年前。 Improve
假设我们在有向图上运行 sharir kosaraju 算法。我们在这张图上有一条弧 (u,v)。在这个算法中,我们有两个 DFS 通过。现在假设我们将顶点 u 插入到第一棵深度树 T 中。v 可以出
在有向图中,要找到强连通分量(使用 Kosaraju 算法),如果我们可以在完成时间之前使用节点的反向列表然后遍历原始图,为什么我们必须转置邻接矩阵(反转所有边的方向) .换句话说,我们会找到所有顶点
我使用的是 mac、4GB RAM 和 CLion IDE。编译器是 Clang。我需要在这个深度优先搜索的递归实现中允许更多的递归(目前在具有 80k 节点的图上失败)。 typedef unord
我为已过截止日期的作业编写了此代码。 此实现完全适用于各种较小的测试用例,并在图表中显示 5 个最大的强连通组件的大小。 但是当我在大约 875714 个顶点的分配数据集上运行它时,它似乎永远执行。
我正在尝试解决 http://www.spoj.com/problems/BOTTOM/ 以下是我要执行的步骤: 1) 使用 Kosaraju 算法找到强连通分量。 2) 考虑一个强连接的组件。考虑一
谁能给我解释一下 Kosaraju 寻找连通分量的算法背后的逻辑? 我已阅读 description ,尽管我不明白反转图上的 DFS 如何检测强连通分量的数量。 def dfs(visited, s
有一个著名的求强连通分量的算法叫做 Kosaraju 算法,它使用两个 DFS 来解决这个问题,并在 θ(|V| + |E|) 时间。 首先,我们对图 (GR) 的补集使用 DFS 来计算顶点的反向后
这是我为 Kosaraju 算法编写的代码的第一部分。 ###### reading the data ##### with open('data.txt') as req_file:
我正在学习 Kosaraju 算法以从这里找到强连通分量 Kosaraju algorithm . 但是我不明白按照完成时间的递减顺序执行 dfs(G^T) 的必要性是什么,即上面链接中第 3 点中提
我无法理解 Kosaraju 用于查找有向图的强连通分量的算法。这是我笔记本上的内容(我是学生 :D): 从任意顶点开始(用#1 标记)并执行 DFS。当你不能再进一步时,用 #2 标记最后访问的顶点
假设我们有一个有向图,它不是一个完整的图并且有多个 SCC。我想知道如果我们转置图形并使用 Kosaraju 算法,强连通分量的模式是否会改变?通过说“转置图形”我的意思是翻转边缘的方向。如果我们尝试
我目前有一个 Kosaraji 算法的工作实现,给定一个没有权重的有向图,将在图中打印 SCC。 我想对其进行调整,以便它也说明 SCC 之间的边缘位置。 代码如下: from collections
Kosaraju 的算法陈述如下: #Input is graph G 1-define G_rev (links in reversed order) 2-Find the finishing ti
我是一名优秀的程序员,十分优秀!