周长 (girth)

girth(G)

返回图的周长。

图的周长是其最短环的长度，如果图是无环的，则周长为无穷大。该算法遵循维基百科页面 [1] 中给出的描述，并在包含 m 条边和 n 个节点的图上以 O(mn) 的时间运行。

参数：

GNetworkX 图

返回：

int 或 math.inf

参考

[1]

维基百科：周长 (Girth)

示例

以下所有示例（除了 P_5）都可以轻松通过维基百科进行检查，维基百科上有这些著名图的相应页面。

>>> nx.girth(nx.chvatal_graph())
4
>>> nx.girth(nx.tutte_graph())
4
>>> nx.girth(nx.petersen_graph())
5
>>> nx.girth(nx.heawood_graph())
6
>>> nx.girth(nx.pappus_graph())
6
>>> nx.girth(nx.path_graph(5))
inf