Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Constructing Spanning Trees

Any traversal of a connected, undirected tree visits all the vertices in that tree, regardless of the node from which the traversal is started. During the traversal certain edges are traversed while the remaining edges are not. Specifically, an edge is traversed if it leads from a vertex that has been visited to a vertex that has not been visited. The set of edges which are traversed during a traversal forms a spanning tree.

The spanning tree obtained from a breadth-first traversal starting at vertex v of graph G is called the breadth-first spanning tree   of G rooted at v. For example, the spanning tree shown in Figure gif (c) is the breadth-first spanning tree of tex2html_wrap_inline72821 rooted at vertex b.

Similarly, the spanning tree obtained from a depth-first traversal is the depth-first spanning tree   of G rooted at v. The spanning tree shown in Figure gif (d) is the depth-first spanning tree of tex2html_wrap_inline72821 rooted at vertex c.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.