DFS (DE PTH Fl RST SEARCH) ALGORITHM
The depth-first search (DFS) algorithm SI.arts with the ini1ial node of graph G and goes deeper until we find
the goal node or the node with no children.
Because of the recursive nature, stack data structure can be used lo implement the DFS algorithm. The process
o f implement ing the DFS is similar to the BFS algorithm.
The step by step process to implement the DFS traversal is given as follows -
I. First, create a stack with the lotal number of vertices in the graph.
2. Now, choose any vertex as Lhe starting point o f traversal, and push that vertex into the stack .
J. After that, push a non-visited vertex (adjacent to the vertex on the top of the stack) to the top of the
stack.
4. Now, repeat steps 3 and 4 until no vertices are left to visit from the vertex on the stack's top.
5. If no vertex is left, go back and pop a vertex from the stack.
6. Repeat steps 2, 3, and 4 until the s tack is empty.
Applications of DFS algorithm
The applications of using the DFS algorith m are given as follows -
o DFS algorithm can be used to implement the topologic.al sorting.
o It can be used lo find the paths between two vertices.
o It can also be used to detect cycles in the graph.
o DFS algorithm is also used for one solution puzzles.
o DFS is used to detennine if a graph is bipartite or not.
Algorithm
0
0 © ~ (0 0 ©
0080 (o)©0~ ---® 000
0 0
® © ~ (0
®~ 0© ®es;~ ©
,-1
0
® ©
® © 2)..-0
P11eudocode
DFS(G,v) ( v is the vertex where the search starts)
Stack S := O; ( start with an empty stack)
, for each verte x u, set visited[u] := false;
push S, v;
wblle (S is not empty) do
u := pop S;
if (nol visited[u]) then
visi ted[u] :- lrue;
for each unvisited neighbour w of u
push S, w;
end if
end while
END DFS()
Example of DFS algorithm
Now, let's understand Lhc working of the DFS algorithm by using an example. In the example given below,
there is a directed graph having 7 vertice;.
Adjacency Lists
A : B. D
B : C. F
C : E. G. H
G : E. H
E : B. F
F:A
D:F
H:A
Now, let's stan examining the graph starting from Node H.
Step 1 - First, push H onto Lbe stack.
I. STACK: H
Step 2 - POP the top element from the stack, i.e., 11, and pr int it Now, PUS! I all the neighbors of 11 onto the
stack that arc in ready state.
I. Print: H]STACK: A
Step 3 - POP the top element from the stack, i.e., A, and print it. Now, P USH all the neighbors of A onto the
stack that are in ready state.
I. Print: A
2. STACK: B, D
Step 4 - POP the top element from the stack, i.e., D, and print it. Now, PUSH all the neighbors of D onto the
stack that are in ready stale.
Advertisement
I. Print: D
2. STACK: 8 , F
Step 5 - POP the top element from the stack. i.e.. F, and print it. Now, PUSH all the neighbors of F onto the
stack that are in rea<ly stale.
The depth-first search (DFS) algorithm SI.arts with the ini1ial node of graph G and goes deeper until we find
the goal node or the node with no children.
Because of the recursive nature, stack data structure can be used lo implement the DFS algorithm. The process
o f implement ing the DFS is similar to the BFS algorithm.
The step by step process to implement the DFS traversal is given as follows -
I. First, create a stack with the lotal number of vertices in the graph.
2. Now, choose any vertex as Lhe starting point o f traversal, and push that vertex into the stack .
J. After that, push a non-visited vertex (adjacent to the vertex on the top of the stack) to the top of the
stack.
4. Now, repeat steps 3 and 4 until no vertices are left to visit from the vertex on the stack's top.
5. If no vertex is left, go back and pop a vertex from the stack.
6. Repeat steps 2, 3, and 4 until the s tack is empty.
Applications of DFS algorithm
The applications of using the DFS algorith m are given as follows -
o DFS algorithm can be used to implement the topologic.al sorting.
o It can be used lo find the paths between two vertices.
o It can also be used to detect cycles in the graph.
o DFS algorithm is also used for one solution puzzles.
o DFS is used to detennine if a graph is bipartite or not.
Algorithm
0
0 © ~ (0 0 ©
0080 (o)©0~ ---® 000
0 0
® © ~ (0
®~ 0© ®es;~ ©
,-1
0
® ©
® © 2)..-0
P11eudocode
DFS(G,v) ( v is the vertex where the search starts)
Stack S := O; ( start with an empty stack)
, for each verte x u, set visited[u] := false;
push S, v;
wblle (S is not empty) do
u := pop S;
if (nol visited[u]) then
visi ted[u] :- lrue;
for each unvisited neighbour w of u
push S, w;
end if
end while
END DFS()
Example of DFS algorithm
Now, let's understand Lhc working of the DFS algorithm by using an example. In the example given below,
there is a directed graph having 7 vertice;.
Adjacency Lists
A : B. D
B : C. F
C : E. G. H
G : E. H
E : B. F
F:A
D:F
H:A
Now, let's stan examining the graph starting from Node H.
Step 1 - First, push H onto Lbe stack.
I. STACK: H
Step 2 - POP the top element from the stack, i.e., 11, and pr int it Now, PUS! I all the neighbors of 11 onto the
stack that arc in ready state.
I. Print: H]STACK: A
Step 3 - POP the top element from the stack, i.e., A, and print it. Now, P USH all the neighbors of A onto the
stack that are in ready state.
I. Print: A
2. STACK: B, D
Step 4 - POP the top element from the stack, i.e., D, and print it. Now, PUSH all the neighbors of D onto the
stack that are in ready stale.
Advertisement
I. Print: D
2. STACK: 8 , F
Step 5 - POP the top element from the stack. i.e.. F, and print it. Now, PUSH all the neighbors of F onto the
stack that are in rea<ly stale.
