Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Spanning Trees and Minimum Spanning Trees

Spanning Trees and Minimum Spanning Trees

What is a (Minimum) Spanning Tree in a graph?

A spanning tree in a graph G=(V,E) is an acyclic, connected subgraph of G, that contains all vertices of G.

A minimum spanning tree in a graph G=(V,E) with weights on the edges is a spanning tree such that the sum of the edge weights of the edges in the tree is minimum.

The LEDA functions

SPANNING_TREE() computes a spanning tree of a given graph G=(V,E) in time O(|V|+|E|).

MIN_SPANNING_TREE() computes a minimum spanning tree of a given graph G=(V,E) in time O(|E|log|E|).

Example of SPANNING_TREE() and MIN_SPANNING_TREE()

See also:

Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Minimum Spanning Trees


Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH