拓扑排序#

topological_sort(G)[source]#

返回按拓扑排序的节点生成器。

拓扑排序是有向图节点的一种非唯一排列，使得从 u 到 v 的边意味着 u 在拓扑排序顺序中出现在 v 之前。此排序仅在图没有有向环时有效。

参数：
GNetworkX 有向图

有向无环图 (DAG)

产生：
节点

按拓扑排序产生节点。

引发：
NetworkXError

拓扑排序仅定义用于有向图。如果图 G 是无向的，则会引发 NetworkXError。

NetworkXUnfeasible

如果 G 不是有向无环图 (DAG)，则不存在拓扑排序，并会引发 NetworkXUnfeasible 异常。如果在处理返回的迭代器期间 G 发生更改，也可能引发此异常。

RuntimeError

如果在处理返回的迭代器期间 G 发生更改。

另请参阅

is_directed_acyclic_graph, lexicographical_topological_sort

说明

此算法基于“算法导论：一种创造性方法” [1] 中的描述和证明。

参考文献

[1]

Manber, U. (1989). Introduction to Algorithms - A Creative Approach. Addison-Wesley.

示例

获取拓扑排序的逆序

>>> DG = nx.DiGraph([(1, 2), (2, 3)])
>>> list(reversed(list(nx.topological_sort(DG))))
[3, 2, 1]

如果你的有向图自然地用边表示任务/输入，用节点表示启动任务的人/过程，那么 topological_sort 可能不是你真正需要的。你需要将任务更改为节点，并用边反映依赖关系。结果是边的一种拓扑排序。这可以使用 networkx.line_graph() 完成，如下所示

>>> list(nx.topological_sort(nx.line_graph(DG)))
[(1, 2), (2, 3)]
在本页