Python使用DFS查找图路径时返回冗余子路径的原因是什么？

你的代码输出冗余路径主要存在两个核心逻辑漏洞：

• 未校验递归子路径有效性：当前代码对所有邻居的递归返回结果直接执行path.extend()操作，没有判断该次递归是否真的找到了通往终点的路径。只要邻居未被访问，不管递归返回的是空列表还是有效路径，都会被追加到当前路径中，导致所有探索过的子路径都被拼接进最终结果。
• 找到有效路径后未终止遍历：当你已经通过某个邻居找到通往终点的路径后，没有跳出循环停止遍历其余邻居，会继续探索其他分支的路径，导致多个分支的路径被拼接在一起。

以你给出的测试用例为例：从节点0先走到节点1，遍历邻居2时找到路径[2,4]，拼接后得到[0,1,2,4]，但代码不会停止，还会继续遍历节点1的下一个邻居3，递归找到[3,4]后再次拼接，才会退回到节点0继续遍历邻居2，再次探索得到[2,4]拼接进去，最终就得到了你看到的[0, 1, 2, 4, 3, 4, 2, 4]冗余结果。

修正后的函数代码 #

def find_path(graph, start, end, visited):
    # 标记当前节点已访问
    if start not in visited:
        visited.append(start)
    # 两节点直接连通的情况直接返回路径
    if graph[start][end] == 1:
        return [start, end]
    # 遍历所有邻居节点
    for neighbour in range(len(graph)):
        if graph[start][neighbour] == 1 and neighbour not in visited:
            # 递归查询子路径
            sub_path = find_path(graph, neighbour, end, visited)
            # 仅当子路径有效时，拼接当前节点后返回，终止剩余分支遍历
            if sub_path:
                return [start] + sub_path
    # 所有邻居都无法通往终点时返回空列表
    return []

测试用例调整 #

你原测试用例中连续两次调用find_path共用了同一个visited列表，第一次调用后visited已被修改，第二次调用时无法正常遍历所有分支，需要每次调用前重置visited：

g1 = [[0, 1, 1, 0, 0],
      [1, 0, 1, 1, 0],
      [1, 1, 0, 0, 1],
      [0, 1, 0, 0, 1],
      [0, 0, 1, 1, 0]]

# 第一次调用
visited = []
print(find_path(g1, 0, 4, visited))

# 第二次调用前重置visited
visited = []
assert find_path(g1, 0, 4, visited) in [[0, 2, 4], [0, 2, 1, 3, 4], [0, 1, 2, 4], [0, 1, 3, 4]]

修正后代码输出结果为[0,1,2,4]（具体路径取决于邻居遍历顺序），符合断言要求。

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