Depth First Search - GATE CSE Notes

Depth-first search (DFS) is a recursive algorithm, and it is also known as depth-first traversal. Traversal means visiting all the nodes of a graph or a tree. The DFS algorithm is used to search the vertices of a tree or a graph, where the traverse begins with the first node or element of a graph and keeps repeating until we get the targeted node or element. As DFS is recursive, the data structure stack can be utilised in its implementation.

Table of Contents

Algorithm
Pseudocode
The Complexity of the Depth-first Search Algorithm
DFS Example

Algorithm:

Stage 1: SET Position = 1 (ready status) for all elements in P

Stage 2: Push X as the starting element on the stack and make Position=2 (staying condition)

Stage 3: Until the stack is blank, reprise stages fourth and fifth.

Stage 4: Pop out the topmost node Y from the stack, function it and MAKE Position=3 (processed state)

Stage 5: Now, Push all the sequel elements of Y having Position=1 and MAKE Position = 2 (staying condition)

[LAST POINT OF LOOP]

Stage 6: EXIT

Pseudocode:

DFS(P, V) ( V is the vertex where the search starts )
Stack S := {}; (At first the stack is blank)
for each vertex X, set visited[X] := false;
push S, V;
while (S is not empty) do
X = pop S;
if (not visited[X]) then
visited[X] = true;
for each unvisited neighbour Y of X
push S, Y;
end if
end while
END DFS()

The Complexity of the Depth-first Search Algorithm

Time Complexity of DFS:

In a graph, let P is the number of vertices and E is the number of edges, so the time complexity is O(P+E).

The space complexity of DFS:

O(P) is the space complexity of DFS.

DFS Example:

Let’s look at an example to better understand how the DFS algorithm functions. Here, there are seven vertices in a graph.

[Adjacency List –

P: R, T

B: S, U

S: V, W, P

W: V, P

U: Q

T: U

P: Q]

Now, let’s traverse the graph beginning with element P.

Phase 1 – Push P on the stack initially.

STACK: P

Phase 2 – POP the stack’s top component P and publish it. Then PUSH all components that are next to P or we can say neighbours of P that are in the ready state onto the stack.

Print: P]STACK: Q

Phase 3 – POP Q the component at the top of the stack, then print it. Now, PUSH all of Q’s neighbours who are in the ready condition onto the stack.

Print: Q

STACK: R, S

Phase 4 – POP the element T at the top of the stack, then display it. Now, from the ready state, PUSH all of T’s neighbours onto the stack.

Print: T

STACK: R, U

Phase 5 – Print the component U at the top of the stack using POP. All of U’s neighbours should now be PUSHED into the stack.

Print: U

STACK: R

Phase 6 – POP the component R at the top of the stack, then print it. Push all of R’s neighbours onto the stack at this point.

Print: R

STACK: S

Phase 7 – POP the component S at the top of the stack, then display it. All of S’s neighbours should now be PUSHED into the stack.

Print: S

STACK: V, W

Phase 8 -PUSH all of W’s neighbours into the stack and POP the top component W off the stack.

Print: W

STACK: V

Phase 9 – Push all of V’s neighbours into the stack and POP the top component V from the stack.

Print: V

STACK:

The stack is now empty, as it is with all vertices.

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.

Also Explore,