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 an undirected graph using Kruskal’s algorithm.

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected graph that connects all vertices together without cycles and with the minimum possible total edge weight.

This function computes the edges that form the MST or forest of an undirected graph. Kruskal’s algorithm works by sorting all the edges in the graph by their weights and then adding them one by one to the MST, ensuring that no cycles are formed.

>>> G = rx.PyGraph()
>>> G.add_nodes_from(["A", "B", "C", "D"])
NodeIndices[0, 1, 2, 3]
>>> G.add_edges_from([(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)])
EdgeIndices[0, 1, 2, 3, 4]
>>> mst_G = rx.minimum_spanning_tree(G, weight_fn=lambda x: x)
>>> mst_G.weighted_edge_list()
WeightedEdgeList[(2, 3, 4), (0, 3, 5), (0, 1, 10)]

In this example, the edge (0, 2, 6) won’t become part of the MST because in the moment it’s considered, the two other edges connecting nodes 0-3-2 are already parts of MST because of their lower weight.

To obtain the result just as a list of edges, see minimum_spanning_edges().

Parameters:

  • graph (PyGraph) – An undirected graph

  • weight_fn –

    A callable object (function, lambda, etc) that takes an edge object and returns a float. This function is used to extract the numerical weight for each edge. For example:

    rx.minimum_spanning_tree(G, weight_fn=lambda x: 1)

    will assign a weight of 1 to all edges and thus ignore the real weights.

    rx.minimum_spanning_tree(G, weight_fn=float)

    will just cast the edge object to a float to determine its 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.

Raises:

ValueError – If a NaN value is found (or computed) as an edge weight.