diameter

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 的大小成线性关系。

Parameters:

GNetworkX 图

seed整数, random_state, 或 None (默认)

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

Returns:

d整数

G 的直径下界

Raises:

NetworkXError

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

See also

networkx.algorithms.distance_measures.diameter

References

[1]

Magnien, Clémence, Matthieu Latapy, and Michel Habib. Fast computation of empirically tight bounds for the diameter of massive graphs. Journal of Experimental Algorithmics (JEA), 2009. https://arxiv.org/pdf/0904.2728.pdf

[2]

Crescenzi, Pierluigi, Roberto Grossi, Leonardo Lanzi, and Andrea Marino. On computing the diameter of real-world directed (weighted) graphs. International Symposium on Experimental Algorithms. Springer, Berlin, Heidelberg, 2012. https://courses.cs.ut.ee/MTAT.03.238/2014_fall/uploads/Main/diameter.pdf

Examples

>>> G = nx.path_graph(10)  # 无向图
>>> nx.diameter(G)
9
>>> G = nx.cycle_graph(3, create_using=nx.DiGraph)  # 有向图
>>> nx.diameter(G)
2