如何获取含环有向图中两点的所有路径，避免DFS遍历死循环

问题背景 #

我目前可通过DFS遍历无环有向图获取两点间的所有路径，无环场景下运行正常，比如测试用例中可得到路径D-C-B-A和D-E-A；但在含环有向图场景下，程序会进入死循环无法输出结果。

核心解决思路 #

避免死循环的核心是在遍历过程中记录当前路径已访问的节点，若下一个待遍历节点已经存在于当前路径中，说明进入环路，直接跳过该分支即可。

实现伪代码 #

# 存储所有符合要求的路径
all_paths = []

def dfs(current_node, target_node, graph, current_path):
    # 当前节点加入路径
    current_path.append(current_node)
    
    # 到达目标节点，保存路径
    if current_node == target_node:
        all_paths.append(current_path.copy())
        current_path.pop()
        return
    
    # 遍历所有邻接节点
    for next_node in graph[current_node]:
        # 核心去环逻辑：下一个节点已在当前路径中，说明有环，跳过
        if next_node in current_path:
            continue
        dfs(next_node, target_node, graph, current_path)
    
    # 回溯移除当前节点
    current_path.pop()

# 调用示例：查找节点D到节点A的所有路径
# graph为邻接表格式存储的图结构
dfs("D", "A", graph, [])

补充说明 #

• 该实现同时兼容无环、含环有向图的全路径遍历需求，无死循环问题
• 可根据业务需要额外增加路径长度限制，比如添加len(current_path) <= 最大路径长度的判断，避免超长路径带来的性能损耗
• 如果有需要我编写的PLSQL语言版本的DFS源代码（代码实现不够简洁优雅），可以留言告知。

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