图全路径查找递归算法：如何避免循环同时允许路径收敛

核心解决思路是给每条路径维护独立的已访问节点记录，而非使用全局的已访问标记——这样既可以避免单条路径内部出现循环，又不会限制不同路径访问同一个节点。

具体实现步骤如下：

• 调整递归函数参数：在递归函数中新增一个参数，用来传递当前路径已经经过的节点集合（或者直接传递当前路径列表，因为路径里的节点就是已访问的）。每次递归调用时，传递的是当前路径的副本，而非修改原有的集合，确保不同路径的已访问记录互不干扰。

• 基准情况处理：当当前节点没有出边时，直接返回包含当前完整路径的列表（当前路径加上该节点）。

• 递归逻辑优化：

  1. 先将当前节点加入到当前路径中，生成新的路径副本；
  2. 遍历当前节点的所有邻接节点：
     • 如果邻接节点不在新的路径副本中，说明这条分支不会形成循环，继续递归调用；
     • 如果邻接节点已经在路径里，直接跳过该节点，避免无限递归；
  3. 收集所有递归返回的子路径，汇总后作为当前节点的结果返回。

伪代码示例 #

function find_all_paths(current_node, current_path):
    # 生成包含当前节点的新路径（副本，不修改原路径）
    new_path = current_path + [current_node]
    
    # 基准情况：当前节点无出边，返回这条完整路径
    if 当前节点没有出边:
        return [new_path]
    
    all_paths = []
    # 遍历所有邻接节点
    for neighbor in current_node 的邻接节点:
        # 检查邻接节点是否已在当前路径中，避免循环
        if neighbor not in new_path:
            # 递归获取从邻接节点出发的所有子路径
            sub_paths = find_all_paths(neighbor, new_path)
            # 把子路径加入结果集
            all_paths.extend(sub_paths)
    
    return all_paths

针对你提到的场景说明 #

比如无环图中节点2和4都需要访问节点5的情况：

• 当处理从节点2出发的路径时，当前路径是[..., 2]，节点5不在其中，所以可以正常递归访问5；
• 当处理从节点4出发的路径时，当前路径是[..., 4]，节点5也不在其中，同样可以正常访问5。
  两条路径的已访问记录是独立的，不会互相限制，完美解决了路径收敛时的冲突问题。

同时，遇到循环场景（比如节点1→2→1）时，当处理节点2的邻接节点1时，1已经在当前路径[1,2]中，会直接跳过该节点，避免无限递归。

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