recursive_simple_cycles#

recursive_simple_cycles(G)[源代码]#

求有向图的简单环（基本电路）。

A simple cycle 或 elementary circuit ，是一个封闭路径，其中没有节点出现两次。如果两个基本电路彼此不是循环排列，则它们是不同的。

此版本使用递归算法来构建循环列表。您可能应该使用名为Simple_Cycle()的迭代器版本。警告：这个递归版本使用了很多内存！它出现在NetworkX中具有教学价值。

参数
G网络X有向图

有向图

返回
循环列表，其中每个循环由节点列表表示
沿着这个循环。
示例：
>>> 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

笔记

该实施遵循第79-80页 [1].

时间复杂性是 \(O((n+e)(c+1))\) 为 \(n\) 节点， \(e\) 边和 \(c\) 初级电路。

工具书类

1

求有向图的所有基本电路。D.B.Johnson，《暹罗计算杂志》，第4期，第1期，第77-84页，1975年。网址：https://doi.org/10.1137/0204007