Next: Algorithms for Planar Graphs Up: Graphs Algorithms Previous: Maximum Weight Matchings in

Minimum Spanning Trees (min_span)

list<edge> SPANNING_TREE(graph G) SPANNING_TREE takes as argument a graph G(V,E). It computes a spanning tree T of the underlying undirected graph, SPANNING_TREE returns the list of edges of T. The algorithm ([52]) has running time O(|V|+|E|).

list<edge> MIN_SPANNING_TREE(graph G, edge_array<int> cost)

MIN_SPANNING_TREE takes as argument an undirected graph G(V,E) and an edge_array cost giving for each edge an integer cost. It computes a minimum spanning tree T of G, i.e., a spanning tree such that the sum of all edge costs is minimal. MIN_SPANNING_TREE returns the list of edges of T. The algorithm ([46]) has running time O(|E| log|V|).

list<edge> MIN_SPANNING_TREE(graph G, int (*cmp)(edge, edge ))

Variant using a function cmp to compare edge costs.

LEDA research project
1998-10-02

list<edge>	SPANNING_TREE(graph G)	SPANNING_TREE takes as argument a graph G(V,E). It computes a spanning tree T of the underlying undirected graph, SPANNING_TREE returns the list of edges of T. The algorithm ([52]) has running time O(\|V\|+\|E\|).
list<edge>	MIN_SPANNING_TREE(graph G, edge_array<int> cost)
		MIN_SPANNING_TREE takes as argument an undirected graph G(V,E) and an edge_array cost giving for each edge an integer cost. It computes a minimum spanning tree T of G, i.e., a spanning tree such that the sum of all edge costs is minimal. MIN_SPANNING_TREE returns the list of edges of T. The algorithm ([46]) has running time O(\|E\| log\|V\|).
list<edge>	MIN_SPANNING_TREE(graph G, int (*cmp)(edge, edge ))
		Variant using a function cmp to compare edge costs.