Depth First Search or DFS for a Graph

Depth First Search (DFS) is a fundamental algorithm used to explore or traverse a graph. It starts at a given node (usually the root or an arbitrary node) and explores as far as possible along each branch before backtracking. DFS is commonly used for tasks like pathfinding, topological sorting, cycle detection, and finding connected components in graphs.

Here’s an overview of how DFS works, both recursively and iteratively:

1. DFS Basics

DFS explores a graph by following these steps:

1. Start at the root node (or any arbitrary node).
2. Visit the current node and mark it as visited.
3. Explore each adjacent (neighboring) node that hasn’t been visited yet.
4. If a neighbor is found that hasn’t been visited, recursively or iteratively explore it.
5. Backtrack when you reach a dead end (i.e., a node with no unvisited neighbors).

This process continues until all nodes have been visited, or the search goal is met.

2. DFS Algorithm (Recursive Approach)

The recursive approach uses the system’s call stack to remember the nodes to visit next. Here’s a general outline for DFS in a graph using recursion:

3. DFS Algorithm (Iterative Approach)

In the iterative version, we use a stack to simulate the call stack instead of recursion. Here’s how you can implement DFS iteratively:

4. DFS Time and Space Complexity

• Time Complexity: $O(V+E)$, where:
  • $V$ is the number of vertices (nodes) in the graph.
  • $E$ is the number of edges. DFS visits every node and edge once, hence the total time complexity is proportional to the sum of the number of vertices and edges.
• Space Complexity: $O(V)$, due to the space required to store the visited set and the recursion stack (in the recursive version) or the explicit stack (in the iterative version).

5. Applications of DFS

• Pathfinding: DFS can be used to find a path from one node to another in an unweighted graph, although BFS (Breadth-First Search) is often more optimal for shortest paths.
• Topological Sorting: In a Directed Acyclic Graph (DAG), DFS is used to perform topological sorting, which orders nodes so that for every directed edge $u\to v$, node $u$ appears before $v$.
• Cycle Detection: DFS can help in detecting cycles in both directed and undirected graphs.
• Finding Connected Components: In an undirected graph, DFS can find all connected components, identifying which nodes are connected.
• Solving Puzzles: DFS is used in problems like mazes, Sudoku, and other search problems, where you explore all possible configurations until a solution is found.

6. DFS Traversal Example

Given the graph:

A DFS traversal starting from node 0 would proceed as follows:

1. Start at node 0 → mark 0 as visited.
2. Visit neighbor 1 → mark 1 as visited.
3. Visit neighbor 3 → mark 3 as visited. Backtrack to node 1.
4. Visit neighbor 4 → mark 4 as visited. Backtrack to node 1, then backtrack to node 0.
5. Visit neighbor 2 → mark 2 as visited.

Thus, the traversal order would be: 0 → 1 → 3 → 4 → 2.

Conclusion

DFS is a versatile and fundamental graph traversal algorithm. Whether using recursion or iteration, it systematically explores all reachable nodes from the starting point. While DFS can be slow for certain applications (especially when you want the shortest path), it is invaluable in tasks like topological sorting, cycle detection, and solving complex search problems.