Tarjan 算法，递归错误

Question

我正在尝试实现 Tarjan 的算法（以在图中找到强连接的组件）。我陷入了算法的 dfs 部分，其中组件计数器无法正确更新自身。我认为这是我的递归方法的问题，但我无法修复它。这是代码：def dfs_scc(graph, node, components_c, nodes_c, connected_components, visited_nodes):    nodes_c+=1    connected_components[node]=-nodes_c    visited_nodes.append(node)    last=nodes_c    for adj in graph.get_adj(node):        if (connected_components[adj[1]]==0):            b=dfs_scc(graph, adj[1], components_c, nodes_c, connected_components, visited_nodes)            last=min(last, b)        elif (connected_components[adj[1]]<0): last=min(last, -connected_components[adj[1]])    if (last==-connected_components[node]):        components_c+=1        print('VISITED NODE QUEUE: ', list(visited_nodes), '; COMPONENTS COUNTER: ', components_c)        while(visited_nodes[-1]!=node):            w=visited_nodes.pop()            connected_components[w]=components_c        w=visited_nodes.pop()        connected_components[w]=components_c    return last这里的输出：VISITED NODE QUEUE: [0, 1, 6, 2, 4, 5, 7] ; COMPONENTS COUNTER: 1VISITED NODE QUEUE: [0, 1, 6, 2, 4, 5] ; COMPONENTS COUNTER: 1VISITED NODE QUEUE: [0, 1, 6] ; COMPONENTS COUNTER: 1 VISITED NODE QUEUE: [3] ; COMPONENTS COUNTER: 1----------------------CONNECTED COMPONENT: {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1}正如您所看到的，被访问节点的队列以正确的顺序删除元素，首先递归节点 7 被弹出当然只是它在那个组件中；在下一次递归中，属于同一组件的节点 2、4 和 5 被删除，依此类推。相反，在输出的最后一行，我有一个字典（节点：组件），其中组件值始终相同。有什么想法吗？

Answer 1

问题是函数执行对components_c,nodes_c进行的修改必须带回调用者的同名变量，但这并没有发生，因为这些变量在它们自己的函数执行上下文中是本地的。具有这些名称的调用者变量不会被它进行的递归调用修改，但它们应该被修改。

你可以用不同的方式解决这个问题。一种方法是做dfs_scc一个定义在 内的函数scc，并且在 的范围内只定义上面提到的两个变量scc。然后dfs_scc可以通过关键字引用这些变量nonlocal而不是将它们作为参数获取，因此以递归树中所有执行上下文都能看到的方式修改它们。

这是它的样子：

def scc(graph):

    components_c=nodes_c=0

    # define the recursive function with the scope where the above variables are defined

    def dfs_scc(graph, node, connected_components, visited_nodes):

        nonlocal components_c, nodes_c # reference those variables

        nodes_c+=1

        connected_components[node]=-nodes_c

        visited_nodes.append(node)

        last=nodes_c

        for adj in graph.get_adj(node):

            if (connected_components[adj[1]]==0):

                b=dfs_scc(graph, adj[1], connected_components, visited_nodes)

                last=min(last, b)

            elif (connected_components[adj[1]]<0):

                last=min(last, -connected_components[adj[1]])

        if (last==-connected_components[node]):

            components_c+=1

            print('VISITED NODE QUEUE: ', list(visited_nodes), '; COMPONENTS COUNTER: ', components_c)

            while(visited_nodes[-1]!=node):

                w=visited_nodes.pop()

                connected_components[w]=components_c

            w=visited_nodes.pop()

            connected_components[w]=components_c

        return last

    #connected_components : {npde0: components, node1: components, node2: components, node3 : components, ...}

    connected_components={graph.get_nodes()[i]: 0 for i in range(len(graph.get_nodes()))}

    visited_nodes=deque()

    for node in graph.get_nodes():

        if (connected_components[node]==0):

            dfs_scc(graph, node, connected_components, visited_nodes)

    return connected_components