Graph Theory Lessons

Lesson 13b: Breadth First Traversal

Quite often when data is held in a tree structure, we want to traverse the tree. This means we want to examine each vertex of the tree and be sure that we did not omit any of them. One strategy is the breadth first traversal. We shall need an ordering of the vertices so that, given a vertex with n children the children can be processed in order. For our purposes we shall assume the children are ordered by vertex label so that if a vertex has child vertices labeled 5 and 7, say, vertex 5 comes before vertex 7. You start at the root of the tree. Then you visit all the immediate children of the root, i.e., the vertices at level 1, starting from the first child of the root to the last one. You then visit the level 2 vertices starting from the first child of the first child of the root and ending with the last child of the last child of the root. You continue in this fashion until all the vertices have been processed. The applet below demonstrates breadth first traversal of a full n-ary tree.

Breadth First Traversal of Full n-ary trees

The same approach works even when the tree is not a full tree. Indeed all we need is a connected graph. In the applet below you will draw your own graph and see a Breadth First Traversal of your graph. Note that the graph needs to be connected but might have cycles, so that it is not a tree. However, the vertices and edges used (picture will be on on the right part of the applet) do comprise a tree. This is a breadth first spanning tree. We shall discuss spanning trees in a later lesson.

Breadth First Traversal of Connected Graphs

(Depth First Traversal on next page...)

e-mail: C. Mawata