[go: up one dir, main page]
Scribd
Upload
41 views5 pages

30 - Data Structure - Depth First Traversal

Uploaded by

laraib
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
41 views5 pages

30 - Data Structure - Depth First Traversal

Uploaded by

laraib
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

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.

You might also like