In the study of graph theory there is a classical problem with an interesting solution. Essentially, the task is for a motion to visit all of the nodes of a ugraph. This process is called traversing the ugraph. The task is made slightly easier if the ugraph is connected (all in one piece). As a by-product the traversing of a connected ugraph will become also be a method for producing a spanning tree of that ugraph.
For clarity visited nodes are colored yellow. Unvisited nodes start out as white. See Fig 2.3a.
The task and its solution may be better understood by discussing a real-life situation. The rooms and corridors of a house follow a simple plan shown in Fig 2.3a. A detective must enter the house through one door and examine cmpletely all of the rooms of a house. Corridors make all rooms accessable. The task concludes with the detective's departure from the house through the same door.
The method of transversing is simple. Go down corridors until he can go no further. (Since the ugraph is a tree, the node will be a leaf.) He enters from the outside with the symbol of a green box. Then he goes down as far as he can go. He passes through three rooms to do this. See Fig 2.3b [1].
His only way out is to backtrack to the previous room. Fig 2.3b [2].
He sees an unvisited room (white node) down another corridor and goes down it as far as he can. Fig 2.3b [3].
There are still two unvisited rooms (two white nodes). So again he backtracks through several rooms. Fig 2.3b [4].
He sees the two yet unvisited rooms and goes down the corridors into them. Fig 2.3b [5].
He backtracks again all the way to the top room where he entered the house.
There are no more unvisited rooms (all nodes are yellow). So he backs out of the house (into the green box).
All the rooms have been visited. Remove the arrows and see that all the nodes are yellow. See Fig 2.3a.
Several points have been omitted to make the explanation simple. Instead of painting a room yellow to indicate it was visited, the detective could drop a piece of yellow paper onto the floor. Then he could look down all the corridors to adjacent rooms to find a room without a yellow paper.
In the discussion above the ugraph was a tree, so there were no problems caused by loops. But the method of applying yellow can be extended to the general ugraph, which most likely will have loops. It is easier to work with labeled ugraphs. Transversing a labeled ugraph is discussed in additional material.