# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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.

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.

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.

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

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

## 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 236 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 268 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 253 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 283 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 326 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 362 of file extended_graph_alg.h.