1

对于给定的有向图G，我需要使用 Kosaraju 算法计算其强连通分量 (SCC)。据我了解，算法的步骤如下：

  1. 让G rev = G将所有弧反转
  2. 在G rev 上运行DFS（深度优先搜索）以计算节点的完成时间
  3. 在G上运行DFS以发现 SCC

我已经设法找到所有节点的正确完成时间。我部分理解我应该将完成时间分配给其各自的节点值，反转图G rev，然后在反转图（现在G ）上再次运行 DFS，完成时间作为节点值处理节点，按完成时间的递减顺序. 我的理解正确吗？如果是这样，我该如何编码？

这是我到目前为止的地方：

# 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？

此外，我迭代而不是递归地执行它的原因是分配的输入文件太大并且程序将达到递归限制。

编辑：在回答问题后，我意识到这个问题不符合课程的荣誉准则。我编辑了问题以排除可能会泄露分配解决方案的部分代码。

4

1 回答 1

1

因为我的问题只是：

用fin_times字典做什么？

我将仅针对该问题提供解决方案，而不是为作业提供完整的解决方案。

所以答案似乎是颠倒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}

然后我们在G个处理节点上按完成时间的递减顺序运行DFS（在本例中，顶点 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...
于 2020-07-23T19:27:02.233 回答