Skip to main content
`Ctrl`+`K`

# random_spanning_tree

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

  Sample a random spanning tree using the edges weights of `G`.

  This function supports two different methods for determining the probability of the graph. If `multiplicative=True`, the probability is based on the product of edge weights, and if `multiplicative=False` it is based on the sum of the edge weight. However, since it is easier to determine the total weight of all spanning trees for the multiplicative version, that is significantly faster and should be used if possible. Additionally, setting `weight` to `None` will cause a spanning tree to be selected with uniform probability.

  The function uses algorithm A8 in [1] .

  Parameters:
    G nx.Graph

      An undirected version of the original graph.

    weight string

      The edge key for the edge attribute holding edge weight.

    multiplicative bool, default=True

      If `True`, the probability of each tree is the product of its edge weight over the sum of the product of all the spanning trees in the graph. If `False`, the probability is the sum of its edge weight over the sum of the sum of weights for all spanning trees in the graph.

    seed integer, random_state, or None (default)

      Indicator of random number generation state. See Randomness.

  Returns:
    nx.Graph

      A spanning tree using the distribution defined by the weight of the tree.

  References

  [1]

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