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...
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:-
A✏B✏E✏F✏C✏F✏E✏G✏H✏E✏B✏A✏A
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 |
A✏B✏E✏F✏C✏F✏E✏G✏H✏E✏B✏A✏A
If you have any query then leave your comments and don't forgot to follow me on Google+,Facebook,Twitter.
COMMENTS