Depth First Search Algorithm

In this article Depth First Search Algorithm (DFS) is a graph traversal algorithm that explores vertices depth-wise using recursion or a stack. Learn DFS algorithm, pseudocode, example, time complexity, applications, advantages, and limitations in a clear and simple way.

Depth First Search Algorithm 

Introduction

Depth First Search (DFS) is a graph traversal algorithm used to explore vertices of a graph.

In DFS, vertices are visited depth-wise along a single path.
The algorithm goes as deep as possible along one branch before backtracking and exploring other branches.

Data Structures Used in DFS

DFS mainly uses:

• Stack, or
• Recursion (Call Stack)

Both help in remembering the previously visited vertices during traversal.

How DFS Algorithm Works

1. Mark the starting vertex as visited
2. Move to one of its unvisited adjacent vertices
3. Continue this process until no unvisited adjacent vertex is available
4. Backtrack to the previous vertex and explore the next unvisited path
5. Repeat until all reachable vertices are visited

DFS Algorithm (Pseudo Code)

DFS(G, v)

mark v as visited

for each vertex u adjacent to v

if u is not visited

DFS(G, u)

Example

If A is the source vertex, one possible DFS traversal order is:

A→B→D→E→C

(The next path is chosen only after the current path is completely explored.)

Features of DFS

• Performs depth-wise traversal
• Uses backtracking
• Each vertex is visited only once
• Can be implemented using recursion or stack

Time and Space Complexity

• Time Complexity: O(V+E)
• Space Complexity: O(V)

Where:

• V = number of vertices
• E = number of edges

Applications of DFS

• Cycle detection in graphs
• Topological sorting
• Finding connected components
• Maze solving / path-finding problems
• Detecting strongly connected components

Advantages and Limitations of DFS

Advantages:

• Uses less memory compared to BFS
• Simple to implement using recursion
• Useful for deep exploration problems

Limitations:

• Shortest path is not guaranteed
• Can face issues in graphs with very large or infinite depth
• May go deep into unnecessary paths

Conclusion

Depth First Search (DFS) is an efficient graph traversal algorithm that explores vertices depth-wise using stack or recursion.
It is widely used in graph theory problems such as cycle detection, topological sorting, and path finding.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1