我正在尝试实现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)
问题是，函数执行带来的修改对 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