minimum_cycle_basis

minimum_cycle_basis(G, weight=None)

返回 G 的最小权重圈基

最小权重是指一个圈基，其中所有圈的总权重（对于无权重图是总长度）最小。

参数:

GNetworkX 图

weight: string

用于边权重的边属性名称

返回:

一个由圈列表组成的列表。每个圈列表是一个由节点组成的列表，

这些节点在 G 中形成一个圈（循环）。请注意，这些节点不一定

按照它们在圈中出现的顺序返回

另请参阅

simple_cycles, cycle_basis

示例

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

参考文献

[1] Kavitha, Telikepalli, et al. “An O(m^2n) Algorithm for Minimum Cycle Basis of Graphs.” http://link.springer.com/article/10.1007/s00453-007-9064-z [2] de Pina, J. 1995. Applications of shortest path methods. Ph.D. thesis, University of Amsterdam, Netherlands