topological_sort#

topological_sort(G)[source]#

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

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

Parameters:
GNetworkX 有向图

一个有向无环图 (DAG)

Yields:
节点

按拓扑排序顺序生成节点。

Raises:
NetworkXError

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

NetworkXUnfeasible

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

RuntimeError

如果在处理返回的迭代器时 G 发生了变化。

See also

is_directed_acyclic_graph, lexicographical_topological_sort

Notes

该算法基于 “Introduction to Algorithms: A Creative Approach” [1] 中的描述和证明。

References

[1]

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

Examples

要获取拓扑排序的反向顺序：

>>> 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)]
On this page