random_spanning_tree

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

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

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

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

Parameters:

Gnx.Graph

原始图的无向版本。

weightstring

边属性的键，用于保存边权重。

multiplicativebool, default=True

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

seedinteger, random_state, or None (default)

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

Returns:

nx.Graph

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

References

[1]

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