Class KruskalMSF

Inheritance Relationships

Base Type

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

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