Python：使用networkx库来实现DAG的构建、拓扑排序

有向无环图（Directed Acyclic Graph，DAG）是一个由一些顶点和有向边组成的有向图，其中任意顶点不能形成环。

DAG常用于表示复杂系统中的依赖关系，例如软件工程中的构建、自然语言处理中的句法结构分析、生物学中的基因表达等。

安装

pip install networkx

示例

import networkx as nx

# 创建有向无环图
G = nx.DiGraph()

# 添加顶点
G.add_node("A")
G.add_node("B")
G.add_node("C")

# 添加有向边: A->B 和 B->C
G.add_edge("A", "B")
G.add_edge("B", "C")

# 查看DAG的顶点
print(G.nodes())
# 输出： ['A', 'B', 'C']

# 查看DAG的边
print(G.edges())
# 输出： [('A', 'B'), ('B', 'C')]

# 进行DAG的拓扑排序
# 拓扑排序可以得到DAG中顶点的一个线性序列，
# 其中任意一条有向边连接的起点在序列中都排在终点之前
order = list(nx.topological_sort(G))
print(order)
# 输出： ['A', 'B', 'C']

参考文章

• 如何在Python中实现DAG（有向无环图）