Depth First Search

Apr 28 • General • 2289 Views • 2 Comments on Depth First Search

Depth First Search

Tree Traversal

Traveling from the start node to find the target node, by visiting all the nodes only once with the available path(edge).

Before we gonna know about DFS we need to know the basics of a tree stucture

A tree is a hierarchical order of nodes that that contains

• ROOT (top node of the tree)
• NODE (all elements in the tree will be considered as NODE)
• PARENT (any node that contain child / children) a ROOT also PARENT if it contains children but we cant consider every PARENT is a ROOT
• CHILD (any node that does not contain child) all the leaf nodes are CHILD
• EDGES (like branches will connect 2 nodes

this is a tipi cal example of a tree

picture of a tree that explains traversal

Depth First Search(DFS)

In depth-first search the idea is to travel as deep as possible from neighbour node to neighbour node before backtracking. What determines how deep is possible is that you must follow edges, and you don’t visit any vertex or node twice.

To do this properly we need to keep track of which vertices have already been visited, plus how we got to (the path to…) where we currently are, so that we can backtrack. We could keep track of which nodes were visited in a boolean array, and a stack to push nodes onto that we mean to visit (the course Readings have a recursive algorithm for DFS which takes a slightly different approach). Here’s some pseudocode:

DFS(T,a) ( a is the vertex where the search starts )
Stack S := {}; ( start with an empty stack )
for each vertex u, set visited[u] := false;
push S, a;
while (S is not empty) do
u := pop S;
if (not visited[u]) then
visited[u] := true;
for each unvisited neighbour w of u
push S, w;
end if
end while
END DFS()

now we can see the traversal in the form of pictorial representation

STEP 1:

Here the ROOT node is A, so the search starts from the ROOT A
with no other node visited
while visiting the node we have to follow the left first order
our mission is to reach node F

step1

STEP 2:

Now we have visited to node B
the path we have traveled: A,B

step2

STEP 3:

Still we have move downwards, till we reach the a CHILD we have to travel downwards
Now we have visited to node D
the path we have traveled: A,B,D

step 3

STEP 4:

now we have reached the CHILD and we haven’t hit our target so from here we have to backtrack and find the non-visited node

path we traveled: A,B,D,H

STEP 5:

here we have reached the CHILD so for we have not reach the target so we have to travel back

i.e :: from H->D and goes to D->E

path travelled :A,B,D,H,E

step 5

STEP 6:

here also we have reached the CHILD so again we have to travel back

no unvisited nodes are available in B so again we have to travel back to A and go to C

i.e :: E->B->A->c

path travelled :A,B,D,H,E,C

Step 6

STEP 7:

now we have visited the TARGET node, node F so we can stop the search

path travelled :A,B,D,H,E,C,F

step 7

and that’s the way to travel from root to target

For more traversal technique
Breath First Search

« Breath First Search Electric circuit- dependent and independent sources »