如何基于元组列表快速构建符合规则的NetworkX有向无环图(DAG)

可以通过建立值到节点的映射字典快速匹配符合条件的边，避免低效的双重遍历，具体步骤如下：

• 先创建一个字典，将每个元组的第一个元素（x值）映射到所有以该值为x的元组（即对应节点）
• 初始化NetworkX的有向图，将所有元组作为节点加入
• 遍历每个元组，用它的第二个元素（y值）去字典里查找所有匹配的目标节点，直接添加有向边

完整代码示例：

import networkx as nx
from collections import defaultdict

# 你的元组列表（示例）
tuple_list = [(0,1), (0,2), (1,3), (4,5), (3,6)]

# 构建x值到对应节点（元组）的映射
x_to_nodes = defaultdict(list)
for t in tuple_list:
    x_to_nodes[t[0]].append(t)

# 初始化有向无环图
dag = nx.DiGraph()

# 添加所有节点
dag.add_nodes_from(tuple_list)

# 批量添加符合条件的有向边
for source in tuple_list:
    y_val = source[1]
    # 获取所有x等于当前y值的目标节点
    targets = x_to_nodes.get(y_val, [])
    for target in targets:
        dag.add_edge(source, target)

# 验证结果（输出所有边）
for edge in dag.edges():
    print(f"边: {edge}")

这种方法利用字典的O(1)查找特性，将整体时间复杂度降到O(n)（n为元组数量），比逐个比对所有元组对的O(n²)方法高效得多，尤其适合元组数量较多的场景。

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