recursive_simple_cycles#

recursive_simple_cycles(G)[source]#

查找有向图的简单环（基本回路）。

一个 简单环，或称 基本回路，是一个封闭路径，其中没有节点出现两次。如果两个基本回路不是彼此的循环置换，则它们是不同的。

此版本使用递归算法构建环列表。您可能应该使用名为 simple_cycles() 的迭代器版本。警告：此递归版本会占用大量内存！它出现在 NetworkX 中是出于教学价值。

参数:
GNetworkX DiGraph

一个有向图

返回:
一个环列表，其中每个环都由一个节点列表表示
沿环的路径。
示例
>>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
    ..

>>> G = nx.DiGraph(edges)
    ..

>>> nx.recursive_simple_cycles(G)
    ..
[[0], [2], [0, 1, 2], [0, 2], [1, 2]]

另请参见

simple_cycles, cycle_basis

注释

此实现遵循 [1] 中第 79-80 页。

时间复杂度为 \(O((n+e)(c+1))\)，其中 \(n\) 为节点数，\(e\) 为边数，\(c\) 为基本回路数。

参考文献

[1]

查找有向图的所有基本回路。D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975. https://doi.org/10.1137/0204007

在本页