Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

rustworkx.minimum_spanning_tree#

minimum_spanning_tree(graph, weight_fn=None, default_weight=1.0)#

Find the minimum spanning tree or forest of a graph using Kruskal’s algorithm.

Parameters:
  • graph (PyGraph) – Undirected graph

  • weight_fn

    A callable object (function, lambda, etc) which will be passed the edge object and expected to return a float. This tells rustworkx/rust how to extract a numerical weight as a float for edge object. Some simple examples are:

    minimum_spanning_tree(graph, weight_fn: lambda x: 1)
    

    to return a weight of 1 for all edges. Also:

    minimum_spanning_tree(graph, weight_fn: float)
    

    to cast the edge object as a float as the weight.

  • default_weight (float) – If weight_fn isn’t specified this optional float value will be used for the weight/cost of each edge.

Returns:

A Minimum Spanning Tree (or Forest, if the graph is not connected).

Return type:

PyGraph

Note

The new graph will keep the same node indices, but edge indices might differ.