Monday, 14 January 2013

Depth First Search


By on 00:34

Depth First Search:-Depth First Search is a major technique which comes in a Traverse scheme of vertex's.This technique is used in c,c++,java,C# etc.

DFS Algorithm:-


Now I discuss this algorithm in step wise. Step 1:-The Starting Vertex is A,initialise all vertex to ready state i.e. status=1.

Step 2:-Push A to stack and change the status to waiting state i.e. status=2.


Step 3:-Repeat Step 4 & 5(until stack=empty).


Step 4:-Pop the top vertex and change the state to process state i.e. status=3.


Step 5:-(a)If status=1 then Push vertex to stack and change the state into waiting  state.


(b)If status=2 then Delete vertex from stack and change the state into Process state.


(c)If status=3 then ignored.


Step 6:-Exit.


Example:-


DFS Algorithm(Tree)



NULL     A
A     B,C,D
B     E,F,C,D
E     F,G,C,D
F     C,G,D
C     G,D
G     H,D
H     D
D     NULL

ABEFCFEGHEBAA


If you have any query then leave your comments and don't forgot to follow me on Google+,Facebook,Twitter.

0 comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...