next up previous contents index
Next: Euler Tours ( euler_tour Up: Graph Algorithms Previous: Stable Matching ( stable_matching   Contents   Index


Minimum Spanning Trees ( min_span )

list< edge> SPANNING_TREE(const 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 ([58]) has running time O(| V| + | E|) .


void SPANNING_TREE1(graph& G) SPANNING_TREE takes as argument a graph G(V, E) . It computes a spanning tree T of the underlying undirected graph by deleting the edges in G that do not belong to T . The algorithm ([58]) has running time O(| V| + | E|) .


list< edge> MIN_SPANNING_TREE(const graph& G, const edge_array< int> & cost)
    MIN_SPANNING_TREE takes as argument a graph G(V, E) and an edge_array cost giving for each edge an integer cost. It computes a minimum spanning tree T of the underlying undirected graph of graph 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 ([52]) has running time O(| E| log| V|) .


list< edge> MIN_SPANNING_TREE(const graph& G, const leda_cmp_base< edge> & cmp)
    A variant using a compare object to compare edge costs.

list< edge> MIN_SPANNING_TREE(const graph& G, int (*cmp)(const edge& , const edge& ))
    A variant using a compare function to compare edge costs.


next up previous contents index
Next: Euler Tours ( euler_tour Up: Graph Algorithms Previous: Stable Matching ( stable_matching   Contents   Index
Christian Uhrig 2017-04-07