recursive_simple_cycles

recursive_simple_cycles(G)

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

一个 简单环 或 基本回路 是一个闭合路径，其中没有节点出现两次。两个基本回路如果它们不是循环排列的，则被认为是不同的。

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

Parameters:

GNetworkX DiGraph

一个有向图

Returns:

一个环列表，其中每个环由沿着该环的节点列表表示。

示例：

>>> 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]]

See also

simple_cycles, cycle_basis

Notes

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

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

References

[1]

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