174 GRAPH THEORY [CHAP. 8
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 seach (DFS) 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 (BFS) will be a QUEUE.
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 atA; that is, we process
a neighbor ofA, then 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 depth-first search (DFS) algorithm appears in Fig. 8-31. The algorithm will process only those vertices
which are connected to the starting vertexA, that is, the connected component includingA. 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 (which we callB) that is still in the ready state (STATE=1). This vertexBcan be obtained by traversing
through the list of vertices.
Remark: The structure STACK in the above algorithm is not technically a stack since, in Step 5(b), we allow
a vertexJto be deleted and then inserted in the front of the stack. (Although it is the same vertexJ, it usually
represents a different edge in the adjacency structure.) If we do not deleteJin Step 5(b), then we obtain an
alternate form of DFS.
Fig. 8-31