214 DIRECTED GRAPHS [CHAP. 9
During the execution of our algorithms, each vertex (node)NofGwill be in one of three states, called the
statusofN, as follows:
STATUS=1:(Ready State) The initial state of the vertexN.STATUS=2:(Waiting State) The vertexNis on a (waiting) list, waiting to be processed.STATUS=3:(Processed State) The vertexNhas been processed.The waiting list for the depth-first search will be a (modified) STACK (which we write horizontally with the TOP
of STACK on the left), whereas the waiting list for the breadth-first search will be a QUEUE.
(a) Depth-first Search:The general idea behind a depth-first search beginning at a starting vertexAis as
follows. First we process the starting vertexA. Then we process each vertexNalong a pathPwhich begins at
A; that is, we process a neighbor ofA, then a neighbor of a neighbor ofA, and so on. After coming to a “dead
end,” that is, to a vertex with no unprocessed neighbor, we backtrack on the pathPuntil we can continue
along another pathP′. And so on. The backtracking is accomplished by using a STACK to hold the initial
vertices of future possible paths. We also need a field STATUS which tells us the current status of any vertex
so that no vertex is processed more than once. The algorithm appears in Fig. 9-12.Fig. 9-12Algorithm 9.2 will process only those vertices which are reachable from a starting vertexA. Suppose one
wants to process all the vertices in the graphG. Then the algorithm must be modified so that it begins again with
another vertex that is still in the ready state (STATE=1). This new vertex, sayB, can be obtained by traversing
through the list of vertices.
Remark: The structure STACK in Algorithm 9.2 is not technically a stack since, in Step 5(b), we allow a vertex
Jto be deleted and then inserted in the front of the stack. (Although it is the same vertexJ, it will represent
a different edge.) If we do not delete the previousJin Step 5(b), then we obtain an alternative traversal algorithm.