Class KruskalMSF¶

Inheritance Relationships¶

Class Documentation¶

class KruskalMSF : public NetworKit::SpanningForest¶

Creates a minimum spanning tree for each connected component.

Public Functions

KruskalMSF(const Graph &G)¶

virtual void run() override¶

Computes for each component a minimum weight spanning tree (or simply a spanning tree in unweighted graphs). Uses Kruskal’s algorithm. Time complexity: sort(n) + n * inverse Ackermann(n, m).

inline edgeweight getTotalWeight() const¶

Returns:

Total edge-weight of the spanning forest. Number of edges in forest if input graph is unweighted.