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: 1

VISITED NODE QUEUE: [0, 1, 6, 2, 4, 5] ; COMPONENTS COUNTER: 1

VISITED 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):&nbsp; &nbsp; components_c=nodes_c=0&nbsp; &nbsp; # define the recursive function with the scope where the above variables are defined&nbsp; &nbsp; def dfs_scc(graph, node, connected_components, visited_nodes):&nbsp; &nbsp; &nbsp; &nbsp; nonlocal components_c, nodes_c # reference those variables&nbsp; &nbsp; &nbsp; &nbsp; nodes_c+=1&nbsp; &nbsp; &nbsp; &nbsp; connected_components[node]=-nodes_c&nbsp; &nbsp; &nbsp; &nbsp; visited_nodes.append(node)&nbsp; &nbsp; &nbsp; &nbsp; last=nodes_c&nbsp; &nbsp; &nbsp; &nbsp; for adj in graph.get_adj(node):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (connected_components[adj[1]]==0):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b=dfs_scc(graph, adj[1], connected_components, visited_nodes)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; last=min(last, b)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; elif (connected_components[adj[1]]<0):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; last=min(last, -connected_components[adj[1]])&nbsp; &nbsp; &nbsp; &nbsp; if (last==-connected_components[node]):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; components_c+=1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print('VISITED NODE QUEUE: ', list(visited_nodes), '; COMPONENTS COUNTER: ', components_c)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while(visited_nodes[-1]!=node):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; w=visited_nodes.pop()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; connected_components[w]=components_c&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; w=visited_nodes.pop()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; connected_components[w]=components_c&nbsp; &nbsp; &nbsp; &nbsp; return last&nbsp; &nbsp; #connected_components : {npde0: components, node1: components, node2: components, node3 : components, ...}&nbsp; &nbsp; connected_components={graph.get_nodes()[i]: 0 for i in range(len(graph.get_nodes()))}&nbsp; &nbsp; visited_nodes=deque()&nbsp; &nbsp; for node in graph.get_nodes():&nbsp; &nbsp; &nbsp; &nbsp; if (connected_components[node]==0):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dfs_scc(graph, node, connected_components, visited_nodes)&nbsp; &nbsp; return connected_components