Class PrimMSF¶

Inheritance Relationships¶

Class Documentation¶

class PrimMSF : public NetworKit::SpanningForest¶

Computes a Minimum Spanning Forest using Prim’s algorithm.

For a given undirected graph, this algorithm grows a forest by greedily adding the smallest edge between visited and unvisited nodes. If the graph is connected, the result is a Minimum Spanning Tree (MST). Otherwise, it yields a forest of MSTs for each connected component.

Public Functions

inline PrimMSF(const Graph &G)¶

Initializes the PrimMSF algorithm for a given graph.

The input graph must be undirected. It may be either weighted or unweighted. In the case of an unweighted graph, each edge is treated as having unit weight.

Parameters:

G – The graph on which the minimum spanning forest will be computed.

Throws:

std::runtime_error – if graph is not an undirected graph

virtual void run() override¶

Runs Prim’s algorithm to compute the minimum spanning forest.

For each connected component of the graph, constructs a minimum spanning tree and computes the total weight of the resulting forest.

inline edgeweight getTotalWeight() const¶

Returns the total weight of the minimum spanning forest.

Returns:

The total weight of the minimum spanning forest.