直径

diameter(G, seed=None)

返回图 G 的直径的下界。

该函数计算有向或无向图 G 的直径（即最大离心率）的下界。所使用的过程取决于图是否为有向图。

如果 G 是一个无向图，则函数使用2-sweep算法 [1]。主要思想是从一个随机节点中选择最远的节点，并返回其离心率。

否则，如果 G 是一个有向图，则函数使用2-dSweep算法 [2]。该过程首先选择一个随机源节点 \(s\)，并从该节点执行一次向前和一次向后 BFS。令 \(a_1\) 和 \(a_2\) 分别为向前和向后情况下的最远节点。然后，它使用向后 BFS 计算 \(a_1\) 的向后离心率，并使用向前 BFS 计算 \(a_2\) 的向前离心率。最后，它返回两者之间最好的下界。

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

参数:

GNetworkX 图

seed整数, random_state, 或 None（默认）

随机数生成状态的指示符。参见 随机性。

返回:

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]

Crescenzi, Pierluigi, Roberto Grossi, Leonardo Lanzi, 和 Andrea Marino。论计算真实世界有向（带权）图的直径。 国际实验算法研讨会。Springer，柏林，海德堡，2012年。https://courses.cs.ut.ee/MTAT.03.238/2014_fall/uploads/Main/diameter.pdf

示例

>>> G = nx.path_graph(10)  # undirected graph
>>> nx.diameter(G)
9
>>> G = nx.cycle_graph(3, create_using=nx.DiGraph)  # directed graph
>>> nx.diameter(G)
2