all_topological_sorts

all_topological_sorts(G)

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

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

参数:

GNetworkX DiGraph

一个有向图

生成:

topological_sort_orderlist

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

引发:

NetworkXNotImplemented

如果 G 不是有向图

NetworkXUnfeasible

如果 G 不是无环图

注意

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

参考文献

[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

示例

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

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