Python图算法：回溯法查找源到目标节点所有路径仅返回单条路径求助

你现有代码的核心问题是使用了visited数组限制每个节点只能被访问一次，该逻辑仅适用于查找无重复节点的简单路径，但你期望的路径允许重复经过环上的节点（比如2→3→4→2、3→4→5→6→3这类环路），所以原有逻辑会直接过滤掉所有需要重复访问节点的路径，最终仅返回1条无重复节点的最短路径。

另外需要注意：由于你的图中存在多个环路，如果不做路径长度限制，理论上可以生成无限多条路径（比如可以循环绕环路任意次再前往终点），因此必须新增路径最大长度约束来避免无限递归。

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def printAllPathsUtil(self, u, d, path, max_path_len): 
        # 把当前节点加入路径
        path.append(u) 

        # 到达终点则打印路径
        if u == d: 
            print(path)
        # 没到终点且路径长度未超过阈值，继续递归
        elif len(path) < max_path_len:
            for i in self.graph[u]: 
                self.printAllPathsUtil(i, d, path, max_path_len) 

        # 回溯移除当前节点
        path.pop()

    def printAllPaths(self, s, d, max_path_len=20): 
        path = [] 
        self.printAllPathsUtil(s, d, path, max_path_len) 


graphData = {1: [2], 2: [3], 3: [4], 4: [2, 5],5: [6, 7], 6: [3], 7: [8], 8: [9], 9: [10]}

g = Graph(10)
for item in graphData:
    for itemx in graphData[item]:
        g.addEdge(int(item), int(itemx))
s = 1
d = 10
# 可根据需要调整最大路径长度，值越大能匹配的绕环次数越多
g.printAllPaths(s, d, max_path_len=20)

运行上述代码后，即可输出你列出的4条路径，如果需要匹配更多绕环次数的路径，适当调大max_path_len的参数值即可。

内容的提问来源于stack exchange，提问作者user8740027