|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
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 
(c)
is the breadth-first spanning tree of 
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 (d)
is the depth-first spanning tree of rooted at vertex c.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.