如何用NetworkX查找给定深度下源到目标的所有非简单路径

NetworkX的nx.all_simple_paths仅能返回无重复节点的简单路径，如果你需要查找指定深度内允许节点重复的所有路径，自定义广度优先搜索（BFS）是最直接简单的实现方式。

问题重现 #

你当前调用nx.all_simple_paths时，在source='A'、target='D'、depth=5的条件下，仅返回路径['A', 'B', 'C', 'D']（3条边），但期望得到包含重复节点的路径如['A', 'B', 'C', 'B', 'C', 'D']（5条边）。

解决方案：自定义BFS遍历路径 #

通过队列实现BFS，追踪每个路径的当前节点和已走路径，当路径长度（边数）达到指定深度时，检查是否到达目标节点，以此枚举所有允许节点重复的路径。

修改后的完整代码 #

import networkx as nx

def create_edges():
    edges = []
    edges.append('A-B')
    edges.append('B-C')
    edges.append('C-B')
    edges.append('C-D')
    return edges

def find_all_paths(g, source, target, max_depth):
    """查找所有边数等于max_depth，且终点为target的路径（允许节点重复）"""
    paths = []
    # 队列元素：(当前节点, 当前路径)
    queue = [(source, [source])]
    
    while queue:
        current_node, current_path = queue.pop(0)
        current_edge_count = len(current_path) - 1
        
        # 路径边数达到指定深度时，检查是否为目标节点
        if current_edge_count == max_depth:
            if current_node == target:
                paths.append(current_path)
            continue
        
        # 边数未达标时，继续扩展邻居节点
        for neighbor in g.neighbors(current_node):
            new_path = current_path.copy()
            new_path.append(neighbor)
            queue.append((neighbor, new_path))
    
    return paths

def get_paths(source, target, depth):
    edges = create_edges()
    g = nx.Graph()
    # 简化图构建：add_edge会自动添加不存在的节点
    for edge in edges:
        n1, n2 = edge.split('-')
        g.add_edge(n1, n2)
    
    # 调用自定义路径查找函数
    path_list = find_all_paths(g, source, target, depth)
    return path_list

res = get_paths('A', 'D', 5)
print(res)
# 输出：[['A', 'B', 'C', 'B', 'C', 'D']]

关键说明 #

1. 路径长度对应关系：传入的depth为路径的边数，比如输出路径包含5条边，与参数depth=5匹配。
2. BFS逻辑：通过队列逐层扩展路径，确保遍历所有可能的节点重复路径。
3. 图构建优化：原代码中手动收集节点的步骤可省略，add_edge会自动添加未存在的节点。

内容的提问来源于stack exchange，提问作者40k-btc