cycle_basis

cycle_basis(G, root=None)

返回构成图 G 环的基础的环列表。

网络的环基础是环的最小集合，使得网络中的任何环都可以表示为基础中环的和。这里的环的和定义为边的“异或”。环基础很有用，例如在使用基尔霍夫定律推导电路方程时。

参数:

GNetworkX 图

root节点, 可选

指定基础的起始节点。

返回:

一个环列表的列表。每个环列表都是一个节点列表

它构成了图 G 中的一个环（回路）。

另请参阅

simple_cycles

minimum_cycle_basis

备注

这是根据算法 CACM 491 [1] 改编的。

参考文献

[1]

Paton, K. An algorithm for finding a fundamental set of cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518.

示例

>>> G = nx.Graph()
>>> nx.add_cycle(G, [0, 1, 2, 3])
>>> nx.add_cycle(G, [0, 3, 4, 5])
>>> nx.cycle_basis(G, 0)
[[3, 4, 5, 0], [1, 2, 3, 0]]