非递归实现Python图结构全路径生成（解决递归深度超限问题）

我有一个包含5000+行的CSV数据集，结构包含Source、Target、Source_repo、Target_repo字段，其中Target5等价于SOURCE5，需要生成所有可能路径（示例：SOURCE1 → Target2、SOURCE8 → Target5 → Target3）。此前使用递归DFS实现时出现maximum recursion depth exceeded错误，现寻求非递归的Python实现方案。

原递归代码的核心问题是Python默认递归深度限制（约1000层），当数据集中存在较长的路径链时，递归调用栈会超出系统限制导致报错。以下是迭代式DFS的替代实现：

完整非递归实现代码 #

import pandas as pd

def build_graph(df):
    """从CSV数据构建邻接表形式的图，处理等价节点逻辑"""
    graph = {}
    for _, row in df.iterrows():
        source = row["Source_repo"]
        target = row["Target_repo"]
        
        # 处理Target5与Source5等价的逻辑，统一节点命名
        if target == "Target5":
            target = "Source5"
        # 如果还有其他等价节点，可在此处添加类似判断
        
        if source not in graph:
            graph[source] = []
        # 避免重复添加相同邻接节点
        if target not in graph[source]:
            graph[source].append(target)
    return graph

def iterative_dfs(graph, start_node, save_all_paths=True):
    """
    迭代式DFS枚举路径
    :param save_all_paths: True则保存所有中间路径（如[A], [A,B]），False仅保存到叶子节点的路径
    """
    paths = []
    stack = [[start_node]]
    
    while stack:
        current_path = stack.pop()
        # 保存当前路径（根据参数选择是否保存中间路径）
        if save_all_paths:
            paths.append(current_path)
        
        current_node = current_path[-1]
        # 若当前节点有邻接节点，继续延伸路径
        if current_node in graph and graph[current_node]:
            for neighbor in reversed(graph[current_node]):
                # 避免循环路径（若业务允许循环可删除此判断）
                if neighbor not in current_path:
                    new_path = current_path.copy()
                    new_path.append(neighbor)
                    stack.append(new_path)
        # 若不保存中间路径，仅在无邻接节点时保存
        elif not save_all_paths:
            paths.append(current_path)
    
    return paths

def enumerate_all_paths(graph):
    """枚举图中所有节点出发的所有路径"""
    all_paths = []
    for node in graph.keys():
        node_paths = iterative_dfs(graph, node)
        all_paths.extend(node_paths)
    return all_paths

if __name__ == "__main__":
    # 读取数据集
    df = pd.read_csv("clean_openstack_evolution.csv")
    
    # 构建图结构
    graph = build_graph(df)
    
    # 生成所有路径
    result = enumerate_all_paths(graph)
    
    # 验证输出（打印前10条路径）
    for idx, path in enumerate(result[:10], 1):
        print(f"路径{idx}: {' → '.join(path)}")

关键说明 #

1. 图构建优化：build_graph函数直接遍历CSV行构建邻接表，同时处理Target5与Source5的等价替换，避免冗余节点；还添加了邻接节点去重逻辑，减少重复路径。
2. 迭代DFS逻辑：用栈模拟递归调用过程，每次从栈顶弹出当前路径，生成新路径后重新压入栈，完全规避递归深度限制。
3. 路径保存策略：通过save_all_paths参数可选择保存所有中间路径（如单个节点、长度为2的路径等），或仅保存到叶子节点的完整路径。
4. 循环避免：代码中默认添加了邻接节点不在当前路径的判断，防止出现无限循环路径（如A→B→A），若业务允许循环可删除该判断。

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