我的遞回函式有問題，希望能在這里得到幫助。
我想撰寫一個函式，其中找到兩個節點之間的所有路徑，該函式在找到解決方案后應停止并輸出第一條路徑。如果此路徑已被找到，該函式應繼續直到找到下一條路徑并再次停止并輸出找到的路徑。
為此，我撰寫了一個函式（或我打算這樣做），它從起始節點開始，然后到其鄰居節點，然后到鄰居節點的鄰居節點等，直到到達結束節點。然后它應該輸出路徑。如果沒有到達結束節點，它應該洗掉最后一個節點并在那里繼續。所以是一種帶回溯的DFS演算法。
我的問題是該函式在找到結束節點后不會停止。我認為這是因為仍有“打開”的功能需要關閉。如果我在代碼底部寫“return pathfind(nknots)”而不是“pathfind(nkots)”，那么我的代碼在到達結束節點時停止，但如果尚未到達結束節點，則不會繼續回溯. 所以在這兩種情況下我都有問題。
有沒有人知道我如何解決這個問題？最好以一種我不必過多更改自己的代碼/想法的方式？
def pathfind(x):
visited.add(x)
if neighbours[x] != {}:
for nknots in neighbours[x]:
if nknots == n:
print("final node is found")
augpath.append(n)
return augpath
elif nknots in augpath or nknots not in neighbours or nknots in visited:
print("Node already in augpath, visited or has no neighbours: ")
continue
else:
augpath.append(nknots)
pathfind(nknots) # pathfind on new node
visited.remove(nknots)
augpath.pop()
uj5u.com熱心網友回復：
如果您希望函式在遇到結束節點時立即停止并回傳路徑，那么您應該使用return陳述句告訴它停止：
def onepath(start, end, neighbours, path=[], visited=None):
if visited is None:
visited = {start}
if start == end:
return path [start]
else:
for n in neighbours[start]:
if n not in visited:
visited.add(n)
p = onepath(n, end, neighbours, path [start], visited)
if p:
return p
return None
如果要查找所有路徑，則應回傳由所有遞回呼叫找到的所有路徑組成的串列：
def allpaths1(start, end, neighbours, path=[], visited=set()):
if start == end:
return [path [start]]
else:
return [p
for n in neighbours[start]
if n not in visited
for p in allpaths1(n, end, neighbours, path [start], visited | {start})
]
請注意，使用 double 進行串列推導的語法for有點笨拙。對于這些型別的函式，我認為最pythonic的方式是使用生成器，而不是串列：
def allpaths2(start, end, neighbours, path=[], visited=set()):
if start == end:
yield path [start]
else:
for n in neighbours[start]:
if n not in visited:
yield from allpaths2(n, end, neighbours, path [start], visited | {start})
neighbours = {1: [2, 3, 4], 2: [1, 3], 3: [1, 2, 4], 4: [1, 3]}
# 1 - 2
# | \ |
# 4 - 3
print(onepath(1, 3, neighbours))
# [1, 2, 3]
print(allpaths1(1, 3, neighbours))
# [[1, 2, 3], [1, 3], [1, 4, 3]]
print(list(allpaths2(1, 3, neighbours)))
# [[1, 2, 3], [1, 3], [1, 4, 3]]
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/344892.html