Depth-First Search (DFS) Algorithm Tutorial

Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. DFS can be implemented recursively or with an explicit stack.

You use DFS to traverse graphs, find connected components, detect cycles, and solve pathfinding problems.

function countComponents(graph, n):
    visited = array of size n, initialized to false
    count = 0

    for v from 0 to n - 1:
        if not visited[v]:
            dfs(graph, v, visited)
            count = count + 1

    return count

function dfs(graph, u, visited):
    visited[u] = true
    for each neighbor v of u:
        if not visited[v]:
            dfs(graph, v, visited)

Connected components: Each time you start a new DFS from an unvisited vertex, you've found a new component.

Recursion limit: For deep graphs, recursive DFS may cause stack overflow. Use iterative DFS with an explicit stack for graphs with depth exceeding $10^4$.

Applications: You use DFS for topological sorting, cycle detection, maze solving, finding connected components, and strongly connected components.

Time complexity: $O(V + E)$ because you visit each vertex once and examine each edge once.

Space complexity: $O(V)$ for the visited array and recursion stack.