random_spanning_tree

random_spanning_tree(G, weight=None, *, multiplicative=True, seed=None)

使用图 G 的边权重采样一个随机生成树。

此函数支持两种不同的方法来确定图的概率。如果 multiplicative=True，概率基于边权重的乘积；如果 multiplicative=False，则基于边权重的总和。然而，由于乘法版本更容易确定所有生成树的总权重，因此速度明显更快，应尽可能使用。此外，将 weight 设置为 None 将导致以均匀概率选择生成树。

此函数使用 [1] 中的算法 A8。

参数:

Gnx.Graph

原始图的无向版本。

weightstring

存储边权重的边属性的键。

multiplicativebool, default=True

如果为 True，则每个树的概率是其边权重的乘积与图中所有生成树权重乘积之和的比值。如果为 False，则概率是其边权重的总和与图中所有生成树权重总和之和的比值。

seedinteger, random_state, or None (default)

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

返回:

nx.Graph

使用由树的权重定义的分布生成的生成树。

参考文献

[1]

V. Kulkarni, Generating random combinatorial objects, Journal of Algorithms, 11 (1990), pp. 185–207