Depth First Search (DFS)

Traverse or search a graph or tree in depthward motion.

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack data structure, either explicitly or via recursion, to keep track of the nodes it needs to visit.

DFS is often used to explore all the nodes and edges in a graph, solve maze problems, or even for topological sorting.

How the Algorithm Works

Here’s how DFS works:

  1. Start at the root node (or any arbitrary node for a graph).
  2. Mark the current node as visited.
  3. Explore each unvisited neighbor of the current node by:
    • Moving to the neighbor.
    • Recursively performing DFS on it.
  4. Backtrack when there are no unvisited neighbors.

I find DFS fascinating because it mimics how a person might explore a maze — diving into a path until it ends, then retracing steps to find new paths.

Time & Space Complexities

  • Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges, because we visit each node and edge once.
  • Space Complexity:
    • O(V) for the recursion stack in the worst case (deep recursion in a graph/tree).
    • For an iterative version, the stack size is also O(V).

When to Use

DFS is particularly useful when:

  • You need to visit all the nodes of a graph or tree.
  • You’re solving problems involving connected components, pathfinding, or cycle detection.
  • A depth-based search is more suitable than breadth-based.

Some common applications include:

  • Detecting cycles in a graph.
  • Finding connected components in an undirected graph.
  • Topological sorting of a directed acyclic graph (DAG).

Code Examples

def dfs(node, visited, adj):
    print(node, end=" ")
    visited[node] = True

    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs(neighbor, visited, adj)

# Example usage
vertices = 5
adj = [
    [1, 2],   # Neighbors of node 0
    [0, 3, 4],# Neighbors of node 1
    [0],      # Neighbors of node 2
    [1],      # Neighbors of node 3
    [1]       # Neighbors of node 4
]

visited = [False] * vertices
print("DFS Traversal: ", end="")
dfs(0, visited, adj)

Problems to Solve

WIP

Resources