如何使用NetworkX快速获取森林中所有叶子到根路径上的叶-节点关联对

核心思路 #

不要从叶子节点反向寻路（会产生大量重复计算），直接从每个根节点出发做遍历，遍历到的所有节点直接和当前根组成配对即可，时间复杂度为O(N)（N为总节点数），11k规模数据可秒出结果。

完整代码 #

你已完成的初始化代码无需修改，新增如下逻辑即可：

import pandas as pd
import networkx as nx

# 原有初始化逻辑，分隔符调整为\s+适配多空格分隔场景
data = pd.read_csv('data.txt', sep="\s+", header=0)
data = data[data['child'] != data['Parent']]
G = nx.from_pandas_edgelist(data, source = 'Parent', target = 'child', create_using = nx.DiGraph())
roots = (v for v, d in G.in_degree() if d==0)

# 核心逻辑
result = []
for root in roots:
    # DFS遍历当前根所在树的所有可达节点
    for node in nx.dfs_preorder_nodes(G, source=root):
        # 跳过根节点自身，与示例输出规则对齐
        if node != root:
            result.append((root, node))

# 打印输出
for pair in result:
    print(f"{pair[0]} {pair[1]}")

# 如需写入文件可使用以下代码
# with open("output.txt", "w", encoding="utf-8") as f:
#     for pair in result:
#         f.write(f"{pair[0]} {pair[1]}\n")

更大规模数据适配建议 #

如果后续数据规模增长到百万级，推荐换用igraph库实现，API逻辑和NetworkX基本一致，运算速度可提升5~10倍，内存占用也更低。

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