我正在嘗試實現(xiàn) Tarjan 的算法（以在圖中找到強連接的組件）。我陷入了算法的 dfs 部分，其中組件計數(shù)器無法正確更新自身。我認為這是我的遞歸方法的問題，但我無法修復它。這是代碼：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}正如您所看到的，被訪問節(jié)點的隊列以正確的順序刪除元素，首先遞歸節(jié)點 7 被彈出當然只是它在那個組件中；在下一次遞歸中，屬于同一組件的節(jié)點 2、4 和 5 被刪除，依此類推。相反，在輸出的最后一行，我有一個字典（節(jié)點：組件），其中組件值始終相同。有什么想法嗎？
1 回答
慕姐8265434
TA貢獻1813條經(jīng)驗 獲得超2個贊
問題是函數(shù)執(zhí)行對components_c,nodes_c進行的修改必須帶回調(diào)用者的同名變量，但這并沒有發(fā)生，因為這些變量在它們自己的函數(shù)執(zhí)行上下文中是本地的。具有這些名稱的調(diào)用者變量不會被它進行的遞歸調(diào)用修改，但它們應該被修改。
你可以用不同的方式解決這個問題。一種方法是做dfs_scc一個定義在 內(nèi)的函數(shù)scc，并且在 的范圍內(nèi)只定義上面提到的兩個變量scc。然后dfs_scc可以通過關鍵字引用這些變量nonlocal而不是將它們作為參數(shù)獲取，因此以遞歸樹中所有執(zhí)行上下文都能看到的方式修改它們。
這是它的樣子：
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
添加回答
舉報
0/150
提交
取消