 # OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

Minimum Spanning Trees

Provides algorithms for minimum spanning trees. More...

## Methods for minimum spanning tree computation

template<typename T >
ogdf::computeMinST (const Graph &G, const EdgeArray< T > &weight, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree using Prim's algorithm. More...

template<typename T >
ogdf::computeMinST (const Graph &G, const EdgeArray< T > &weight, NodeArray< edge > &pred, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree (MST) using Prim's algorithm. More...

template<typename T >
void ogdf::computeMinST (const Graph &G, const EdgeArray< T > &weight, NodeArray< edge > &pred)
Computes a minimum spanning tree (MST) using Prim's algorithm. More...

template<typename T >
void ogdf::computeMinST (node s, const Graph &G, const EdgeArray< T > &weight, NodeArray< edge > &pred)
Computes a minimum spanning tree (MST) using Prim's algorithm. More...

template<typename T >
ogdf::computeMinST (node s, const Graph &G, const EdgeArray< T > &weight, NodeArray< edge > &pred, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree (MST) using Prim's algorithm. More...

template<typename T >
ogdf::makeMinimumSpanningTree (Graph &G, const EdgeArray< T > &weight)
Reduce a graph to its minimum spanning tree (MST) using Kruskal's algorithm. More...

## Detailed Description

Provides algorithms for minimum spanning trees.

## ◆ computeMinST() [1/5]

template<typename T >
 T ogdf::computeMinST ( const Graph & G, const EdgeArray< T > & weight, EdgeArray< bool > & isInTree )
inline

Computes a minimum spanning tree using Prim's algorithm.

Template Parameters
 T is the numeric type for edge weights.
Parameters
 G is the input graph. weight is an edge array with the edge weights. isInTree is assigned the result, i.e. isInTree[e] is true iff edge e is in the computed MST.
Returns
the sum of the edge weights in the computed tree.

Definition at line 273 of file extended_graph_alg.h.

## ◆ computeMinST() [2/5]

template<typename T >
 void ogdf::computeMinST ( const Graph & G, const EdgeArray< T > & weight, NodeArray< edge > & pred )
inline

Computes a minimum spanning tree (MST) using Prim's algorithm.

Template Parameters
 T is the numeric type for edge weights.
Parameters
 G is the input graph. weight is an edge array with the edge weights. pred is assigned for each node the edge from its parent in the MST.

Definition at line 306 of file extended_graph_alg.h.

## ◆ computeMinST() [3/5]

template<typename T >
 T ogdf::computeMinST ( const Graph & G, const EdgeArray< T > & weight, NodeArray< edge > & pred, EdgeArray< bool > & isInTree )
inline

Computes a minimum spanning tree (MST) using Prim's algorithm.

Template Parameters
 T is the numeric type for edge weights.
Parameters
 G is the input graph. weight is an edge array with the edge weights. isInTree is assigned the result, i.e. isInTree[e] is true iff edge e is in the computed MST. pred is assigned for each node the edge from its parent in the MST.
Returns
the sum of the edge weights in the computed tree.

Definition at line 291 of file extended_graph_alg.h.

## ◆ computeMinST() [4/5]

template<typename T >
 void ogdf::computeMinST ( node s, const Graph & G, const EdgeArray< T > & weight, NodeArray< edge > & pred )

Computes a minimum spanning tree (MST) using Prim's algorithm.

Template Parameters
 T is the numeric type for edge weights.
Parameters
 s is the start node for Prim's algorithm and will be the root of the MST. G is the input graph. weight is an edge array with the edge weights. pred is assigned for each node the edge from its parent in the MST.

Definition at line 322 of file extended_graph_alg.h.

## ◆ computeMinST() [5/5]

template<typename T >
 T ogdf::computeMinST ( node s, const Graph & G, const EdgeArray< T > & weight, NodeArray< edge > & pred, EdgeArray< bool > & isInTree )

Computes a minimum spanning tree (MST) using Prim's algorithm.

Template Parameters
 T is the numeric type for edge weights.
Parameters
 s is the start node for Prim's algorithm and will be the root of the MST. G is the input graph. weight is an edge array with the edge weights. pred is assigned for each node the edge from its parent in the MST. isInTree is assigned the result, i.e. isInTree[e] is true iff edge e is in the computed MST.
Returns
the sum of the edge weights in the computed tree.

Definition at line 368 of file extended_graph_alg.h.

## ◆ makeMinimumSpanningTree()

template<typename T >
 T ogdf::makeMinimumSpanningTree ( Graph & G, const EdgeArray< T > & weight )

Reduce a graph to its minimum spanning tree (MST) using Kruskal's algorithm.

Template Parameters
 T is the numeric type for edge weights.
Parameters
 G is the input graph. weight is an edge array with the edge weights.
Returns
the sum of the edge weights in the computed tree.

Definition at line 399 of file extended_graph_alg.h.