Kosaraju算法——计算SCCs
Kosaraju algorithm - computing SCCs
对于给定的有向图 G 我需要使用 Kosaraju 算法计算其强连通分量 (SCC)。据我了解算法的步骤如下:
- 令Grev = G所有弧都反转
- 运行 DFS(深度优先搜索)在 Grev 上计算节点的完成时间
- 运行 DFS 在 G 上发现 SCC
我找到了所有节点的正确结束时间。我部分理解我应该将完成时间分配给其各自的节点值,反转图 Grev,并在反转图上再次 运行 DFS(现在 G) 以完成时间为节点值,按完成时间的递减顺序处理节点。我的理解正确吗?如果是这样,我该如何编码?
这是我到目前为止的进展:
# Number of elements in graph + 1
graph_elem = 10
def dfs_iterative(graph):
# variable initialization
for i in range(graph_elem - 1, 0, -1):
stack.append(i)
while stack:
v = ... # Get top of stack
# If the top of the stack is not explored, or if any of the children of
# the node on the top of the stack are unexplored, then continue the traversal
if ...:
#Mark explored
for head in graph[v]:
if head not in explored:
stack.append(head)
# Prevent the loop iterating through all of the children like BFS
else:
# Get finishing time for v
return finishing_times
# Graph represented in a list through edges
# index represents the tail node of the edge, and g[index] is the head node
# Example edges of g: (1, 4), (2, 8), (3, 6), etc.
g = [[], [4], [8], [6], [7], [2], [9], [1], [5, 6], [7, 3]]
rev_g = [[], [7], [5], [9], [1], [8], [3, 8], [4, 9], [2], [6]]
fin_times = dfs_iterative(rev_g)
fin_times
应该是 {3: 1, 5: 2, 2: 3, 8: 4, 6: 5, 9: 6, 1: 7, 4: 8, 7: 9}
,如前所述,它是正确的。我现在和 fin_times
有什么关系?
另外,我迭代而不是递归地做它的原因是赋值的输入文件太大,程序会达到递归限制。
编辑:回答问题后我意识到问题不符合课程的荣誉守则。我编辑了问题以排除可能泄露作业解决方案的部分代码。
因为我的问题只是:
What to do with the fin_times
dictionary?
我将只提供该问题的解决方案,而不是提供作业的完整解决方案。
所以答案似乎是颠倒 fin_times
字典,使键成为值,反之亦然:
order = dict((v, k) for k, v in finishing_times.items())
{1: 3, 2: 5, 3: 2, 4: 8, 5: 6, 6: 9, 7: 1, 8: 4, 9: 7}
然后我们 运行 DFS 在 G 上按完成时间的降序处理节点(在本例中顶点 7 与完成时间 9).对应问题中的代码,而不是:
for i in range(graph_elem - 1, 0, -1):
stack.append(i)
我们写:
order = dict((v, k) for k, v in finishing_times.items())
for i in range(graph_elem - 1, 0, -1):
vertex = order[i]
if vertex not in explored:
stack.append(vertex)
explored.add(vertex)
// DFS code and SCC size computation...
对于给定的有向图 G 我需要使用 Kosaraju 算法计算其强连通分量 (SCC)。据我了解算法的步骤如下:
- 令Grev = G所有弧都反转
- 运行 DFS(深度优先搜索)在 Grev 上计算节点的完成时间
- 运行 DFS 在 G 上发现 SCC
我找到了所有节点的正确结束时间。我部分理解我应该将完成时间分配给其各自的节点值,反转图 Grev,并在反转图上再次 运行 DFS(现在 G) 以完成时间为节点值,按完成时间的递减顺序处理节点。我的理解正确吗?如果是这样,我该如何编码?
这是我到目前为止的进展:
# Number of elements in graph + 1
graph_elem = 10
def dfs_iterative(graph):
# variable initialization
for i in range(graph_elem - 1, 0, -1):
stack.append(i)
while stack:
v = ... # Get top of stack
# If the top of the stack is not explored, or if any of the children of
# the node on the top of the stack are unexplored, then continue the traversal
if ...:
#Mark explored
for head in graph[v]:
if head not in explored:
stack.append(head)
# Prevent the loop iterating through all of the children like BFS
else:
# Get finishing time for v
return finishing_times
# Graph represented in a list through edges
# index represents the tail node of the edge, and g[index] is the head node
# Example edges of g: (1, 4), (2, 8), (3, 6), etc.
g = [[], [4], [8], [6], [7], [2], [9], [1], [5, 6], [7, 3]]
rev_g = [[], [7], [5], [9], [1], [8], [3, 8], [4, 9], [2], [6]]
fin_times = dfs_iterative(rev_g)
fin_times
应该是 {3: 1, 5: 2, 2: 3, 8: 4, 6: 5, 9: 6, 1: 7, 4: 8, 7: 9}
,如前所述,它是正确的。我现在和 fin_times
有什么关系?
另外,我迭代而不是递归地做它的原因是赋值的输入文件太大,程序会达到递归限制。
编辑:回答问题后我意识到问题不符合课程的荣誉守则。我编辑了问题以排除可能泄露作业解决方案的部分代码。
因为我的问题只是:
What to do with the
fin_times
dictionary?
我将只提供该问题的解决方案,而不是提供作业的完整解决方案。
所以答案似乎是颠倒 fin_times
字典,使键成为值,反之亦然:
order = dict((v, k) for k, v in finishing_times.items())
{1: 3, 2: 5, 3: 2, 4: 8, 5: 6, 6: 9, 7: 1, 8: 4, 9: 7}
然后我们 运行 DFS 在 G 上按完成时间的降序处理节点(在本例中顶点 7 与完成时间 9).对应问题中的代码,而不是:
for i in range(graph_elem - 1, 0, -1):
stack.append(i)
我们写:
order = dict((v, k) for k, v in finishing_times.items())
for i in range(graph_elem - 1, 0, -1):
vertex = order[i]
if vertex not in explored:
stack.append(vertex)
explored.add(vertex)
// DFS code and SCC size computation...