直径

diameter(G, seed=None)

返回图G的直径的下界。

该函数计算有向或无向图G的直径(即最大偏心率)的下界。所使用的步骤因有向图或无向图而异。

如果G是一个 undirected 图形，则该函数使用 2-sweep 演算法 [1]. 其主要思想是从随机节点中选取最远的节点并返回其偏心率。

否则，如果G是一个 directed GRAPH，该函数使用 2-dSweep 演算法 [2], 该过程从选择随机源节点开始 \(s\) 从其执行前向和后向BFS。让我们 \(a_1\) 和 \(a_2\) 在向前和向后情况下分别是最远的节点。然后，计算其向后偏心率 \(a_1\) 使用后向BFS和前向偏心率 \(a_2\) 使用前向BFS。最后，它返回两者之间的最佳下限。

在这两种情况下，时间复杂度都与G的大小成线性关系。

参数

G网络X图表

seed整数、随机状态或无（默认）

随机数生成状态的指示器。见 Randomness .

返回

d整数

关于G的直径的下界

加薪

NetworkXError

如果该图是空的，或者如果该图是无向的且没有连通的，或者如果该图是有向的且不是强连通的。

参见

networkx.algorithms.distance_measures.diameter

工具书类

1

Magnien，Clémence，Matthieu Latapy和Michel Habib。 巨型图直径经验紧界的快速计算。 《实验算法杂志》(JEA)，2009。Https://arxiv.org/pdf/0904.2728.pdf

2

克雷森齐、皮尔路易吉、罗伯托·格罗西、莱昂纳多·兰齐和安德里亚·马里诺。 On computing the diameter of real-world directed (weighted) graphs. 国际实验算法研讨会。施普林格，柏林，海德堡，2012年。Https://courses.cs.ut.ee/MTAT.03.238/2014_fall/uploads/Main/diameter.pdf