使用Python-Networkx高效统计两个有向图的公共路径

核心优化思路 #

不要分别遍历两个图的路径再做比对，所有公共简单路径的边必然同时存在于两个图中，因此先抽取两图的公共边构建公共子图，所有公共路径的统计都在公共子图上完成，从根源上剪掉仅存在于单个图的无效边，避免生成无意义的路径，计算量可以降低1~2个数量级。

基础实现（支持按路径长度分类，内存恒定） #

这个实现不需要把全量路径加载到内存，边遍历生成器边计数，内存占用不会随路径总量上涨，完全适配百节点规模的图：

import networkx as nx
from collections import defaultdict

def count_common_paths_by_length(G, H, src, dst):
    # 构建两图的公共边子图
    Gh = nx.DiGraph()
    Gh.add_nodes_from(G.nodes & H.nodes)
    Gh.add_edges_from(set(G.edges) & set(H.edges))
    
    # 提前剪枝：公共子图中两点不连通则直接返回空结果
    if src not in Gh or dst not in Gh or not nx.has_path(Gh, src, dst):
        return defaultdict(int)
    
    len_count = defaultdict(int)
    # 遍历公共子图的简单路径生成器，边遍历边计数，不存储全量路径
    for path in nx.all_simple_paths(Gh, source=src, target=dst):
        # 路径长度默认按边数计算（n个节点对应n-1条边），按节点数统计可去掉-1
        path_len = len(path) - 1
        len_count[path_len] += 1
    return len_count

实现细节说明：

• 提前做连通性判断，省去无意义的路径遍历开销
• 遍历路径时只做计数累加，不存储路径本身，遍历完成的路径直接被回收，不会出现list()转换导致的内存溢出问题
• 直接在公共子图上生成路径，不需要额外做两个图的路径比对，结果天然就是两图共有的路径

进一步性能优化（适用于路径总量极大的场景） #

如果公共子图中两点间路径量过大，连遍历所有路径生成器的耗时都无法接受，可以放弃生成具体路径的all_simple_paths接口，改用分层BFS做纯计数，不需要生成具体路径对象，效率会有量级提升：

• 核心逻辑：从src出发做广度优先搜索，每一层对应固定的路径长度，维护每个节点在当前长度下的路径计数，每扩展一步就把计数传递给邻接节点，遇到dst就把当前计数累加到对应长度的结果中，搜索过程中跳过已访问节点保证路径是简单无环的。
• 这种方式不需要构造每一条路径的节点列表，只做数值计数，哪怕路径总数到百万级也能快速跑完。

如果需要统计全图所有节点对的公共路径，直接在公共子图上用动态规划做递推：初始化长度为1的路径计数就是邻接矩阵，之后每一步长度的路径计数用邻接矩阵和上一步的计数矩阵做递推，跳过成环的路径，一次性就能算出所有节点对、所有长度的公共路径数，比循环每个节点对单独统计效率高很多。

原方案的性能问题 #

你之前分别生成G和H的路径生成器再比对的思路，存在两个明显的性能浪费：

• 会生成大量仅存在于单个图的无效路径，这些路径从一开始就不可能成为公共路径，白白消耗计算资源
• 路径比对本身也有额外开销，如果要做去重统计，还是需要把其中一个图的路径全量存到集合里，内存压力极大

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