all_topological_sorts

all_topological_sorts(G)

返回一个生成器，生成有向图 G 的所有拓扑排序。

拓扑排序是节点的非唯一排列，使得从 u 到 v 的边意味着 u 在拓扑排序顺序中出现在 v 之前。

Parameters:

GNetworkX DiGraph

一个有向图

Yields:

topological_sort_orderlist

G 中节点的一个列表，表示一种拓扑排序顺序

Raises:

NetworkXNotImplemented

如果 G 不是有向的

NetworkXUnfeasible

如果 G 不是无环的

Notes

实现了[1]中给出的算法的迭代版本。

References

[1]

Knuth, Donald E., Szwarcfiter, Jayme L. (1974). “A Structured Program to Generate All Topological Sorting Arrangements” Information Processing Letters, Volume 2, Issue 6, 1974, Pages 153-157, ISSN 0020-0190, https://doi.org/10.1016/0020-0190(74)90001-5. Elsevier (North-Holland), Amsterdam

Examples

枚举有向图的所有拓扑排序：

>>> DG = nx.DiGraph([(1, 2), (2, 3), (2, 4)])
>>> list(nx.all_topological_sorts(DG))
[[1, 2, 4, 3], [1, 2, 3, 4]]