NetworkX DiGraph 从源节点出发满足依赖约束的遍历算法咨询

核心匹配算法 #

直接采用NetworkX内置的拓扑排序算法，对应方法为nx.topological_sort，完全适配你提出的所有遍历约束。

适配逻辑说明 #

拓扑排序针对无环有向图的输出规则，与你的需求一一对应：

• 对任意有向边u -> v，输出序列中节点u的位置必然早于v，保证依赖关系不颠倒——完全覆盖你提到的“被依赖节点先访问，依赖节点不能在前置节点之前”的硬约束，比如子图中目标节点不会在所有上游输入节点之前被访问
• 无相互依赖关系的平行节点，排序顺序无强制要求——对应你提到的“同层节点不管先后顺序都合规”的规则
• 排序过程自动从无入边的源节点（即你定义的data sources）启动，不需要手动识别遍历起点
• 算法通用适配所有你提到的图结构：反向树、直线链路、多分支关联结构、正向非反向树均可正确处理，且你已经确认图中不存在环，不会触发环检测的异常。

现有代码的改造实现 #

你当前拆分弱连通子图的流程可以保留，只需补充子图提取、拓扑排序的逻辑即可，完整可运行代码如下：

import networkx as nx
from networkx.algorithms.components import weakly_connected_components

g = nx.DiGraph()
for i in range(0, 23):
    g.add_node(i)

g.add_edge(13,12)
g.add_edge(9, 8)
g.add_edge(3, 10)
g.add_edge(5, 13)
g.add_edge(7, 11)
g.add_edge(9, 14)
g.add_edge(7, 15)
g.add_edge(7, 16)
g.add_edge(17, 18)
g.add_edge(18, 19)
g.add_edge(3, 20)
g.add_edge(3, 22)
g.add_edge(18, 22)
g.add_edge(22, 21)

# 移除无连接的孤立节点
g.remove_node(0)
g.remove_node(1)
g.remove_node(2)
g.remove_node(4)
g.remove_node(6)

# 遍历每个独立弱连通子图
for component_nodes in weakly_connected_components(g):
    # 从原图提取对应子图
    sub_graph = g.subgraph(component_nodes)
    # 生成符合依赖规则的遍历序列
    traversal_sequence = list(nx.topological_sort(sub_graph))
    # 此处可替换为实际的节点处理逻辑
    print(f"当前子图遍历顺序: {traversal_sequence}")

约束匹配校验 #

所有你提出的硬约束均可被满足：

• 举例的子图4场景：只要节点4.7存在来自4.1、4.5的入边，节点4.4存在指向4.5的入边，排序结果必然保证4.1、4.5在4.7之前，4.4在4.5之前
• 同层无依赖节点的先后顺序不做强制限制，完全符合你提到的“顺序不做固定要求”的规则
• 遍历起点自动定位为子图内无入边的源节点，不存在从中间节点启动遍历的问题

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