如何遍历NetworkX DiGraph节点 满足多源DAG祖先优先处理规则

你需要的遍历规则就是拓扑排序的标准定义，NetworkX原生提供了直接可用的API，无需自己实现遍历逻辑：

• 无需指定单个源点，API会自动识别DAG中所有入度为0的节点作为初始遍历源点
• 天然保证任意节点仅在其所有前驱（祖先）节点都完成遍历后才会被返回
• 直接返回节点序列，不需要额外从边遍历结果中提取节点

基础使用示例 #

import networkx as nx

# 构造示例多源DAG，其中1、2为两个独立源点
dag = nx.DiGraph()
dag.add_edges_from([
    (1, 3), (2, 3), 
    (3, 4), (2, 5)
])

# 直接调用拓扑排序方法即可得到符合要求的遍历序列
for node in nx.topological_sort(dag):
    # 此处执行你的节点处理逻辑
    print(f"处理节点：{node}")

可选拓展 #

如果需要自定义多个源点之间的遍历先后顺序，可以使用nx.lexicographical_topological_sort()方法，通过传入key参数调整优先级规则，示例如下：

# 按节点数值从小到大优先选择源点遍历
for node in nx.lexicographical_topological_sort(dag, key=lambda x: x):
    print(node)

注意事项 #

调用前建议先校验图的合法性，避免因为存在环导致遍历失败：

if not nx.is_directed_acyclic_graph(dag):
    raise ValueError("输入图不是合法DAG，无法执行拓扑排序")

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