當存在回圈時，是否可以使用 DFS 遍歷圖中的所有連接節點？
g = {'a':['b','c'],
'b':['a','f'],
'c':['a','f'],
'd':['c','e'],
'e':['d'],
'f':['c','b'],
}
def dfs(graph, node):
stack = [node]
visited = []
while stack:
current = stack.pop()
visited.append(current)
next_nodes = list(filter(lambda x: x not in visited, graph[current]))
stack.extend(next_nodes)
return visited
dfs(g,'a')
>>>
['a', 'c', 'f', 'b', 'b']
我的解決方案無法達到 d 或 e。它還訪問 b 兩次，這很奇怪。如何更改此代碼以遍歷所有節點（如果可能）而不重復訪問的陣列？
uj5u.com熱心網友回復：
您需要檢查給定節點是否已經在堆疊上，否則您可能最終會處理同一節點兩次：
def dfs(graph, node):
stack = [node]
visited = []
while stack:
current = stack.pop()
visited.append(current)
next_nodes = list(filter(lambda x: x not in visited stack, graph[current]))
stack.extend(next_nodes)
return visited
至于某些節點未被訪問的問題，所有可到達的節點都沒有到或'a'的外向鄰居。如果您的圖表是無向的，您需要確保為每個節點添加所有正確的條目。如果您的圖表是定向的，這是預期的行為。'd''e'
我們也可以優化這段代碼。您可以維護一個單獨的seen集合，以便能夠更快地檢查您是否看到了一個節點（看到==“在堆疊上或已經訪問過”）：
def dfs(graph, node):
stack = [node]
seen = {node}
visited = []
while stack:
current = stack.pop()
visited.append(current)
next_nodes = list(filter(lambda x: x not in seen, graph[current]))
stack.extend(next_nodes)
seen.update(next_nodes)
return visited
這輸出：
['a', 'c', 'f', 'b']
uj5u.com熱心網友回復：
您在將節點放入堆疊時檢查它是否被訪問，但僅在從堆疊中彈出時才將其標記為已訪問。這意味著堆疊上的任何節點都可以再次被推入堆疊（因為此時它們還沒有被標記為已訪問）。
您需要更改visited為seen或類似的內容，以注意它們已添加到堆疊中，并將其添加到堆疊中，next_nodes而不是在訪問時添加節點，或者更改next_nodes生成方式以僅獲取以下節點既不在visited也不stack。
無關地，出于性能原因，我會制作visiteda set，而不是 a 。list
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/477415.html
上一篇：在串列串列中查找子字串