Depth First Search (DFS)
1. Introduction
Depth First Search (DFS) is one of the most fundamental graph traversal algorithms. It explores a
graph by starting from a source vertex and moving as deep as possible along each branch before
backtracking. DFS is widely used in solving problems such as cycle detection, topological sorting,
path finding, and connected components.
2. Concept of DFS
DFS works on the principle of LIFO (Last In First Out) using either:
• Recursion (implicit stack), or
• Explicit stack (non-recursive approach)
DFS starts from a selected node, marks it as visited, visits an adjacent unvisited node, and continues
this process until no further unvisited nodes exist. It then backtracks to the previous node to continue
the search.
3. Characteristics of DFS
1. Deep traversal – explores depth before breadth
2. Uses Stack – recursive stack or explicit stack
3. Backtracking – returns when no more adjacent nodes
4. Time Complexity:
o O(V + E) for adjacency list
5. Space Complexity:
o O(V) due to recursion/stack
6. Useful for complex problems like cycles, ordering, components etc.
4. DFS Algorithm (Recursive Method)
Algorithm
DFS(G, v):
mark v as visited
for each vertex u adjacent to v:
if u is not visited:
DFS(G, u)
Explanation
• Begin at node v
• Mark it visited
• Explore all its unvisited neighbors recursively
• Backtrack when no neighbor is left
5. DFS Using Stack (Iterative Method)
Algorithm
Push start node into stack
While stack is not empty:
Pop node from stack
If not visited:
mark visited
push all adjacent unvisited nodes
6. Example
Consider the following graph:
A -- B -- D
| |
C E
Steps of DFS starting from A
1. Visit A
2. Visit B
3. Visit D
4. Backtrack to B
5. Visit E
6. Backtrack to A
7. Visit C
DFS Traversal Output:
A→ B→ D→ E→ C
7. Applications of DFS
1. Detecting Cycles in Graphs
DFS checks if there is any back-edge, which indicates a cycle.
2. Topological Sorting
DFS is used in Directed Acyclic Graphs (DAGs) to generate topological order.
3. Finding Connected Components
In undirected graphs, DFS helps to identify all connected components.
4. Path Finding
DFS is used to find any path between two vertices.
5. Solving Maze Problems
DFS is used to explore all possible paths in puzzles and mazes.
6. Tree Traversals
In trees, DFS is used for preorder, inorder and postorder traversals.
7. Articulation Point & Bridge Detection
DFS-based algorithms help find critical points and bridges in networks.
8. Advantages of DFS
• Requires less memory compared to BFS
• Useful for solving complex graph problems
• Easy to implement with recursion
• Good for problems requiring deep search
9. Disadvantages of DFS
• May get stuck in deep recursion for large graphs
• Not suitable for finding shortest path
• Backtracking overhead may slow performance
• For infinite graphs, DFS may go into infinite loop without visited-check
DFS Program in C
#include <stdio.h>
int visited[20];
int a[20][20];
int n;
void DFS(int v) {
visited[v] = 1;
printf("%d ", v);
for (int i = 1; i <= n; i++) {
if (a[v][i] == 1 && visited[i] == 0) {
DFS(i);
}
}
}
int main() {
int start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix:\n");
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
}
}
// initialize visited array
for (int i = 1; i <= n; i++) {
visited[i] = 0;
}
printf("Enter starting vertex: ");
scanf("%d", &start);
printf("DFS Traversal: ");
DFS(start);
return 0;
}