Data Structure - Depth First
Traversal
Bhabani Shankar Pradhan
Depth First Search (DFS) algorithm traverses a graph in a depthward motion
and uses a stack to remember to get the next vertex to start a search, when a
dead end occurs in any iteration.
As in the example given above, DFS algorithm traverses from S to A to D to G
to E to B first, then to F and lastly to C. It employs the following rules.
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it.
Push it in a stack.
Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It
will pop up all the vertices from the stack, which do not have adjacent
vertices.)
Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.
Step Traversal Description
1 Initialize the stack.
Mark S as visited and put it
onto the stack. Explore any
unvisited adjacent node
from S. We have three
2
nodes and we can pick any
of them. For this example,
we shall take the node in an
alphabetical order.
Mark A as visited and put it
onto the stack. Explore any
unvisited adjacent node
3 from A. Both S and D are
adjacent to A but we are
concerned for unvisited
nodes only.
Visit D and mark it as
visited and put onto the
stack. Here, we
have B and C nodes, which
4
are adjacent to D and both
are unvisited. However, we
shall again choose in an
alphabetical order.
We choose B, mark it as
visited and put onto the
stack. Here B does not have
5
any unvisited adjacent
node. So, we pop B from
the stack.
We check the stack top for
return to the previous node
and check if it has any
6
unvisited nodes. Here, we
find D to be on the top of
the stack.
Only unvisited adjacent
node is from D is C now. So
7
we visit C, mark it as visited
and put it onto the stack.
As C does not have any unvisited adjacent node so we keep popping the stack
until we find a node that has an unvisited adjacent node. In this case, there's
none and we keep popping until the stack is empty.
