Depth First Search (DFS) is also a linear time graph search algorithm like BFS. It comes with its own set of unique applications.

Working

DFS explores a graph by going as deep as possible along each branch before backtracking. You can implement this in two ways:

1. Using a Stack

   You manually simulate the call stack using a stack data structure. This gives you full control over the traversal order and avoids recursion limits.

   Here is a rough outline of the algorithm:

   • Push the starting node onto a stack.
   • While the stack isn’t empty: • Pop the top node. • If it’s not visited, mark it visited. • Push all its unvisited neighbors onto the stack.

   DFS_Iterative(Graph, start):
   
       create empty stack S
       create set Visited
   
       push start onto S
   
       while S is not empty:
           node = pop S
   
           if node not in Visited:
               add node to Visited
               process(node)
   
               for each neighbor in Graph.adjacent(node):
                   push neighbor onto S

2. Using Recursion

   This is used where the system call stack can be relied on the remember the path.

   Here is a rough outline of the algorithm:

   • Start at a node.
   • Mark it visited.
   • Recursively call DFS on each unvisited neighbor.

   One way to implement the “Mark it visited” step is to use a list of the nodes. Then, we can mark the node as visited by creating a boolean list of length element that stores true in index i if the node with index i has already been visited.

   DFS(Graph, node, Visited):
   
       add node to Visited
       process(node)
   
       for each neighbor in Graph.adjacent(node):
           if neighbor not in Visited:
               DFS(Graph, neighbor, Visited)

When working with Binary Trees, DFS can be classified into pre-order, post-order and in-order traversal.

The running time of DFS is \(O(|V|+|E|)\). It runs in linear time which is why it is incredibly fast.

For each node (u), we iterate over its adjacency list. Then the total cost of iterating over all adjacency lists is proportional to the sum of their lengths:

or

Thus, neighbor iteration contributes (O(E)). Now, in the worst case, each vertex is visited exactly once. Each recursive call corresponds to one vertex.

• Total recursive calls: \(V\).
• Cost per call: constant overhead + adjacency list iteration.
• Total recursive overhead: \(O(V)\).

In the context of a general graph, the space complexity is \(O(|V|)\).

This is because the in the worst case, the stack may need to store all the vertices at a particular level, which can amount to all or nearly all vertices in the graph.

Here is how we can get the space complexity:

• Visited array: \(O(V)\).
• Recursion stack: In the worst case (path graph), recursion depth = \(V\).
• Total auxiliary space: \(O(V)\).

In reality, the space usage won’t always be \(O(V)\). Instead, it will be the maximum distance of any node from the source. This allows us to perform tighter analysis is certain cases.

Warning

The complexity of DFS is different for adjacency matrices. This is because the algorithm does not know how many vertices connect to the present vertex. Thus, it must scan every possible vertex to check if an edge exists.

This leads to a complexity of \(O(V^2)\), regardless of how many edges actually exist.

Both adjacency matrices and lists behave the same logically, but the underlying representation changes the cost of enumerating neighbors.

Warning II

DFS can only be applied to graphs with cycles if you mark nodes as visited. Without this there is a risk it gets stuck in a cycle.

Edge Traversal

In a standard Depth-First Search (DFS) algorithm, edges are not visited twice in the same direction, and the total number of edge traversals is controlled to ensure a linear time complexity. 

In a directed graph, each edge is checked and traversed (if the destination node hasn't been visited) exactly once.

In an undirected graph, each edge, say between nodes u and v, is examined twice: once when exploring the neighbors of u and again when exploring the neighbors of v.

This means we can count edges by incrementing a counter. There are two ways to go about this:

• Count tree edges only (edges used to discover new vertices)
• Count all traversed edges (including backtracking)

These can be selected based on the problem we are solving. If we want to find all unique edges, then we need a way to keep track of the unique edges seen so far.

The most efficient universal method is to assign unique IDs to edges and track them with a boolean array. This avoids hashing and ensures constant-time checks for both directed and undirected graphs.

Here is how we can encode IDs:

• Directed: id = u * n + v
• Undirected: id = min(u,v) * n + max(u,v)

Refer to Assorted Problems for example use cases for this operation.

Example Problems

Depth-first search is ideal for problems where the solution depends on the hierarchical structure of the graph revealed by the DFS tree, particularly ancestor–descendant relationships, finish times, and the organization of reachable subgraphs.

All these algorithms adapt DFS and they do so by doing either of the following:

1. Do something before visiting neighbours (pre-order operations)
2. Do something after visiting neighbours (post-order operations)

If BFS is about distance, DFS is about structure. This is because DFS imposes a temporal structure on the graph. This is why DFS is useful when we want to reveal:

Reachability and connectivity

• s, t-Reachability - Just traverse and determine whether \(t\) can be reached by traversal
• Connected components - can be modelled as Graph Colouring (Flood-Filling) where all the vertices in one connected component are coloured the same colour
• Strongly connected components (SCC)
• Cycle detection - If at any point in the traversal, we reach a node we have already visited that , there must be a cycle
• Path existence

Ordering constraints

• Topological sorting
• Finding linear extensions of partial orders
• Scheduling with dependencies

Graph decomposition

• Biconnected components
• Articulation points
• Bridges
• Dominator trees (with modifications)

Implicit search spaces

• Backtracking (N-queens, Sudoku, permutations)
• Searching state spaces
• Parsing expressions (recursive descent)

DFS gives you:

• A tree structure (the DFS forest)
• A temporal structure (discovery/finish times)
• A stack structure (current path)
• A classification of edges (tree/back/forward/cross)

This is the foundation of most algorithms that leverage DFS. We look at a few of these below.

Cycle Detection

To detect a cycle in a directed graph, we use Depth First Search (DFS). In DFS, we go as deep as possible from a starting node. If during this process, we reach a node that we’ve already visited in the same DFS path, it means we’ve gone back to an ancestor — this shows a cycle exists.

To avoid this issue, we keep track of the parent node — the node from which we reached the current node in DFS. When we move from u to v, we mark u as the parent of v. Now, while checking the neighbors of v, If a neighbor is not visited, we continue DFS for that node. If a neighbor is already visited and not equal to the parent, it means there’s another path that leads back to this node — and hence, a cycle exists.

Refer to how this can be done using BFS: Cycle Detection

Cycle Detection on Directed Graphs

This extends the previous problem to handle directed graphs, which come with their own set of challenges.

Here is the core ideas: in a directed graph, a cycle exists if during DFS traversal we encounter a node that is already in the current recursion stack (i.e., we revisit a node before finishing its exploration).

To fix this, we use two arrays:

• visited[] - marks nodes visited at least once.
• recStack[] - marks nodes currently in the recursion (active) path.

  This is the best approach to implement the algorithm with (because nodes have fixed and consecutive IDs). Using a Hash-Table to give us worst-case \(O(n)\) retrieval is also possible, as is using a stack to keep track with \(O(n)\) retrieval.

If during DFS we reach a node that’s already in the recStack, we’ve found a path from the current node back to one of its ancestors, forming a cycle.

As soon as we finish exploring all paths from a node, we remove it from the recursion stack by marking recStack[node] = false. This ensures that only the nodes in the current DFS path are tracked.

# Utility DFS function to detect cycle in a directed graph
def isCyclicUtil(adj, u, visited, recStack):

    # node is already in recursion stack cycle found
    if recStack[u]:
        return True

    # already processed no need to visit again
    if visited[u]:
        return False

    visited[u] = True
    recStack[u] = True

    # Recur for all adjacent nodes
    for v in adj[u]:
        if isCyclicUtil(adj, v, visited, recStack):
            return True

    # remove from recursion stack before backtracking
    recStack[u] = False
    return False


# Function to detect cycle in a directed graph
def isCyclic(adj):
    V = len(adj)
    visited = [False] * V
    recStack = [False] * V

    # Run DFS from every unvisited node
    for i in range(V):
        if not visited[i] and isCyclicUtil(adj, i, visited, recStack):
            return True
    return False

• Time: (O(V + E)) (each vertex and edge is visited once).
• Space: (O(V)) (for visited set and recursion stack).

Some implementations use three sets (White, Grey, Black):

• White: unvisited nodes.
• Grey: nodes in the current DFS path.
• Black: fully explored nodes.

A cycle is detected if DFS encounters a Grey node again.

Topological Ordering

A function that uses DFS can be written to create a topological ordering in a DAG (a topological sort does not exist for all graphs).

A topological ordering can be defined as an assignment \(f(v)\) of every vertex v to a different number such that:

We can find a topological ordering for every Directed Acyclic Graph (DAG)

DFS is useful because it naturally discovers dependencies through its recursion stack. When DFS finishes exploring a node, all nodes reachable from it have already been processed.

The idea is to perform a DFS traversal starting from every unvisited vertex (from 0 to n − 1). For each DFS call, we first explore all unvisited neighbors of the current node. Once the recursive calls for all its neighbors are complete, we start pushing these nodes into a data structure while backtracking. After all vertices are processed, we pop elements from the data structure one by one into a list — this gives a valid topological ordering, as each node is placed before all nodes it points to.

The ideal data structure for this purpose would be a stack implemented with a linked list to which we can “prepend” elements.

Here is a rough sketch of the algorithm:

1. Run DFS from every unvisited node.
2. When a node finishes (i.e., all outgoing edges explored), push it onto a stack.
3. After DFS completes, reverse the stack → topological order.

Alternatively we can maintain a counter that counts from the number of edges to zero and assigns values in order of the vertices that it encounters.

def findTopoSort(node, vis, adj, stack):
    vis[node] = 1
    for it in adj[node]:
        if vis[it] == 0:
            findTopoSort(it, vis, adj, stack)
    
    # push the node after all its neighbours
    stack.append(node)

def topoSort(adj):
    n = len(adj)
    stack = []
    vis = [0] * n

    for i in range(n):
        if vis[i] == 0:
            findTopoSort(i, vis, adj, stack)

    topo = []
    
    # popping elements from stack and 
    # pushing into the list
    while stack:
        topo.append(stack.pop())
    
    return topo


def addEdge(adj, u, v):
    adj[u].append(v)

An alternate formulation of the algorithm involves calls to dfs_get_visited_list(G, s, visited_list, topolist): which runs recursively to explore unexplored graph segments.

Example Problems

This is a very commonly used algorithm in dependency scheduling. It helps us come up with a sequence of steps we need to follow.

Strongly Connected Components

The goal is to partition the graph into maximal sets of nodes where each node can reach every other.

More specifically, we need to find strongly connected components of a graph.

Here is how the strongly connected components are defined:

A strongly connected component (SCC) of a directed graph is a maximal subgraph where every vertex is reachable from every other vertex.

Nodes in the same SCC form a cycle, meaning a directed path exists between any pair of nodes. SCCs partition directed graphs into distinct, highly connected, and separate subgraphs. 

We will go through a few ways to find SCCs:

Kosaraju

Kosaraju’s algorithm has two main ideas: first, run DFS on the original graph and record vertices by finishing time; second, reverse all edges and run DFS again in that finishing-time order to uncover SCCs.

Here is a rough sketch of the algorithm:

1. Run DFS on the original graph, recording nodes in decreasing order of finish time.
2. Reverse all edges.
3. Process nodes in order of decreasing finish time, running DFS on the reversed graph.
4. Each DFS tree in step 3 is one SCC.

This works because the node with the largest finish time must belong to a “source SCC” in the condensation graph.

Kosaraju’s algorithm runs in linear time O(V+E) for an adjacency-list graph, because it performs two full traversals: one of the graph and one of its transpose. The extra space is O(V+E) if you include the transpose graph, or O(V) additional bookkeeping beyond the graph storage.

Tarjan’s

Tarjan's algorithm is a highly efficient graph algorithm used to find Strongly Connected Components (SCCs) in a directed graph using a single Depth First Search (DFS) traversal. It maintains a stack of visited nodes and uses ids (discovery time) and low-link (lowest node reachable) values to identify the "root" of each SCC when backtracking.

Example Problems

The idea of SCC is key in directed graphs because the usual notion of a connected component does not apply. This it is useful to solve related problems.

For example, we can figure out that a directed graph has the property “every node can reach every other node” if and only if it has exactly one strongly connected component (SCC).

Backtracking

Backtracking is a general problem-solving paradigm that systematically searches for solutions by incrementally building a potential solution and abandoning ("backtracking" from) any partial solution that violates the problem's constraints, thereby exploring only feasible paths in a search space

The backtracking approach uses recursion to explore all possible choices: for each element, you can either include it in the current subset or not. This builds a decision tree, and each leaf node is a valid subset.

Thinking of it as DFS, we can directly implement a recursive solution.

The search space is often a large, implicitly defined decision tree. It is used to explore the search space of possible solutions for combinatorial problems like the N-Queens puzzle or Sudoku. 

Here is a rough sketch for how you can implement it:

function backtrack(state, choices, results):
    if is_solution(state):
        record_solution(state, results)
        // May return here if only one solution is needed
    
    for choice in choices:
        if is_valid(state, choice): // Pruning happens here
            make_choice(state, choice) // Trial
            backtrack(state, next_choices, results) // Recurse (DFS)
            undo_choice(state, choice) // Retreat/Backtrack

Counting Vertices

The standard modification to DFS to find the number of vertices in the connected component being traversed goes as follows:

function DFS_count(v, visited):
    visited[v] = true
    count = 1
    
    for each neighbor u of v:
        if not visited[u]:
            count += DFS_count(u, visited)
    
    return count

This is useful to figure out the tree properties of a graph and to find the largest connected component in a graph.

Assorted Problems

Biconnected Components

Biconnected components are maximal sets of edges where any two edges lie on a common simple cycle. Finding them involves a DFS that tracks discovery times and low-link values, using a stack to store edges. When an articulation point condition is met (root with multiple children or non-root with low[u] ≥ disc[v]), the edges forming a biconnected component are popped from the stack.

Eulerian Path/Circuit

Determines whether an Eulerian path (uses every edge exactly once) exists. For an undirected graph, an Eulerian circuit exists iff all vertices have even degree and the graph is connected (ignoring isolated vertices). An Eulerian path exists iff exactly zero or two vertices have odd degree. The algorithm counts edges traversed during DFS to verify connectivity and compute degrees.

Spanning Tree Weight

Computes the total weight of a spanning tree (if the graph is connected) by performing a DFS and summing the weights of tree edges. It returns the weight if the DFS visited all vertices (graph connected), otherwise indicates failure.

Graph Diameter Calculation

Here is a description of the problem: Diameter.

Approximates the diameter (longest shortest path) of a tree or unweighted graph using two DFS traversals. Here is how it works:

function approximateDiameter(Graph):
    // First DFS: find farthest node from vertex 0
    visited = array false for all vertices
    function DFS_farthest(v, dist):
        <DFS to determine distance>

    (_, endpoint1) = DFS_farthest(0, 0)

    // Second DFS: find farthest node from endpoint1
    reset visited
    (diameter, _) = DFS_farthest(endpoint1, 0)

    return diameter

This works because of the following theorem:

Suppose that \(a\) and \(b\) are the endpoints of the path in the tree which achieve the diameter, and without loss of generality assume that \(a\) and \(b\) are the unique pair which do so. Let s be any vertex in \(T\). A single BFS will return either \(a\) or \(b\) (or both) as the vertex whose distance from s is greatest.

Maze Solving / Path Finding

Finds the shortest path from start to end in a maze (grid or graph) using DFS with backtracking. It explores all paths, keeping track of the number of edges traversed, and records the minimum number of edges to reach the target. This is essentially a brute-force search; for unweighted graphs, BFS would be more efficient for shortest path, but DFS with edge counting can still be used when exploring all paths is needed (e.g., for counting paths or finding longest path).

This is O(V + E) in worst case (explores all paths), but due to backtracking it may explore many paths; still each edge is considered each time it's visited, so worst-case exponential for general graphs, but for trees or mazes without cycles it's O(V+E).

For graphs with cycles, the visited reset ensures all simple paths are explored, leading to exponential time. So not the same as vanilla DFS unless the graph is a tree.

Network Reliability (Bridges)

Identifies bridges (critical edges) whose removal disconnects the graph. Uses a DFS that computes discovery times and low-link values for each vertex. An edge (v,u) is a bridge if low[u] > disc[v] (i.e., no back edge from the subtree of u connects to v or an ancestor).

Singly Connected Graph

A directed graph is singly connected if, for every pair of vertices \((u, v)\), there is at most one simple path from \(u\) to \(v\).

This can be done in time \(O(|V ||E|)\).

To do this, first perform a topological sort of the vertices. Then, we will contain for each vertex a list of it’s ancestors with in degree 0. We compute these lists for each vertex in the order starting from the earlier ones topologically. Then, if we ever have a vertex that has the same degree 0 vertex appearing in the lists of two of its immediate parents, we know that the graph is not singly connected. however, if at each step we have that at each step all of the parents have disjoint sets of degree 0 vertices as ancestors, the graph is singly connected. Since, for each vertex, the amount of time required is bounded by the number of vertices times the in degree of the particular vertex, the total runtime is bounded by O(|V ||E|).