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 被删除，依此类推。

相反，在输出的最后一行，我有一个字典（节点：组件），其中组件值始终相同。

有什么想法吗？

这里要求的是全部代码：

class Graph(object):
    def __init__(self, graph=None):
        if graph == None: graph = {}
        self.__graph = graph

    def get_nodes(self): return list(self.__graph.keys())

    def get_edges(self): return self.__generate_edges()

    def __generate_edges(self):
        edges = []
        for node in self.__graph:
            for adj in self.__graph[node]:
                if node!=adj: edges.append((node, adj))
        return edges

    def add_node(self, node):
        if node not in self.__graph: self.__graph[node] = []

    def add_edge(self, edge):
        if edge[0] in self.__graph: self.__graph[edge[0]].append(edge[1])
        else:self.__graph[edge[0]] = [edge[1]]

    def get_adj(self, node):
        adj=[]
        for edge in self.__generate_edges():
            if node==edge[0] and edge[0]!=edge[1]: adj.append(edge)
        return adj

def scc(graph):
    #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()))}
    components_c=nodes_c=0
    visited_nodes=deque()
    for node in graph.get_nodes():
        if (connected_components[node]==0):
            dfs_scc(graph, node, components_c, nodes_c, connected_components, visited_nodes)
    return connected_components


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


def main():
    g={0: [1, 2], 1: [6], 2: [4], 3: [], 4: [5], 5: [2, 7], 6: [0], 7: []}
    graph=Graph(g)
    # nodes=random.randint(1, 10)
    # for i in range(nodes): graph.add_node(i)
    # for i in range(0, nodes):
    #     for j in range(0, nodes):
    #         graph.add_edge((i, j))
    cc=scc(graph)
    print("CONNECTED COMPONENTS: ", cc)

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

Tarjan 算法，递归错误

Tarjan algorithm, recursion mistakes

python

algorithm

recursion

depth-first-search