tpl_spanning_tree.H File Reference

Spanning tree generation algorithms. More...

#include <tpl_graph.H>
#include <tpl_graph_utils.H>
#include <ah-errors.H>

Include dependency graph for tpl_spanning_tree.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Find_Depth_First_Spanning_Tree< GT, SA >
	Compute a depth-first spanning tree of a graph. More...
class	Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >
	Compute a breadth-first spanning tree of a graph. More...
class	Aleph::Build_Spanning_Tree< GT >
	Build a spanning tree from an array of arcs. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Spanning tree generation algorithms.

Constructs spanning trees using DFS or BFS traversal. For minimum spanning trees, see Prim.H and Kruskal.H.

Features

• DFS spanning tree
• BFS spanning tree (shortest paths in unweighted graphs)
• Random spanning tree

Complexity: O(V + E)

See also

Prim.H Minimum spanning tree

Kruskal.H Minimum spanning tree

Author

Leandro Rabindranath León

Definition in file tpl_spanning_tree.H.