All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
NetworKit::KruskalMSF Class Reference

Creates a minimum spanning tree for each connected component. More...

#include <KruskalMSF.h>

Public Member Functions

 KruskalMSF (const Graph &G)
 
virtual ~KruskalMSF ()=default
 
virtual void run () override
 Computes for each component a minimum weight spanning tree (or simply a spanning tree in unweighted graphs). More...
 
- Public Member Functions inherited from NetworKit::SpanningForest
 SpanningForest (const Graph &G)
 
virtual ~SpanningForest ()=default
 
Graph generate ()
 Deprecated. More...
 
Graph getForest ()
 

Additional Inherited Members

- Protected Attributes inherited from NetworKit::SpanningForest
const GraphG
 
Graph forest
 

Detailed Description

Creates a minimum spanning tree for each connected component.

Constructor & Destructor Documentation

NetworKit::KruskalMSF::KruskalMSF ( const Graph G)
virtual NetworKit::KruskalMSF::~KruskalMSF ( )
virtualdefault

Member Function Documentation

void NetworKit::KruskalMSF::run ( )
overridevirtual

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).

Reimplemented from NetworKit::SpanningForest.


The documentation for this class was generated from the following files: