Depth First Search (DFS) Algorithm for Graphs

Depth First Search (DFS) graph traversal ka doosra primary algorithm hai jo source vertex se start karke kisi ek branch me tab tak depth me aage badhta hai jab tak dead-end na aa jaye ya already visited vertex na mil jaye. Dead-end aane par yeh Backtrack karta hai aur previous branch ke unvisited paths explore karta hai.

DFS Algorithm (Recursive)

DFS_VISIT(u, visited, adj)
1. Mark visited[u] = TRUE
2. Print u
3. For each neighbor v in adj[u] do:
4.     If visited[v] == FALSE then:
5.         DFS_VISIT(v, visited, adj)

DFS(G)
1. Initialize visited[V] = {FALSE}
2. For each vertex v in V do:
3.     If visited[v] == FALSE then:
4.         DFS_VISIT(v, visited, adj)

Graph:
        (0) ---- (1) ---- (2)
         |                 |
        (3) -------------- (4)

DFS Traversal from 0:
Visit 0 -> Go deep to 1 -> Go deep to 2 -> Go deep to 4 -> Go deep to 3
Output: 0 -> 1 -> 2 -> 4 -> 3

Complexity and Applications

• Time Complexity: O(V + E) using Adjacency List.
• Space Complexity: O(V) recursion call stack space.
• Applications: Topological Sorting (DAGs), Strongly Connected Components (Kosaraju / Tarjan algorithm), Cycle detection in directed/undirected graphs, Maze solving.

Agli post me hum Hashing start karenge: Hashing: Hash Tables and Hash Functions.