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_edges#

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

Find the edges in 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]
>>> rx.minimum_spanning_edges(G, weight_fn=lambda x: x)
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 as a graph, see minimum_spanning_tree().

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_edges(G, weight_fn=lambda x: 1)

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

rx.minimum_spanning_edges(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:

The $N - | c |$ edges of the Minimum Spanning Tree (or Forest, if $| c | > 1$ ) where $N$ is the number of nodes and $| c |$ is the number of connected components of the graph.

Return type:

WeightedEdgeList

Raises:

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