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:

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
```
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)
```

<aside> 💡

The visited array is essential to prevent infinite loops and to ensure that each node and edge is processed at most once.

</aside>

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:

$$ \sum_{u \in V} \text{deg}(u) = 2E \quad \text{(for undirected graphs)} $$

$$ \sum_{u \in V} \text{outdeg}(u) = E \quad \text{(for directed graphs)} $$

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)$.

Component	Cost
Marking visited	(O(V))
Iterating neighbors	(O(E))
Recursive overhead	(O(V))
Total Time	(O(V+E))
Space (visited+stack)	(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.

Representation	Time Complexity	Explanation
Edge List	$O(V + E \cdot V) ≈ O(VE)$	For each vertex, finding neighbors requires scanning all edges.
Adj. Matrix	$O(V^2)$	Each step requires scanning a full row $(O(V))$, repeated across all vertices.
Adj. List	$O(V + E)$	Each vertex and edge is processed once; neighbors are accessed directly.

<aside> 💡

An interesting point to consider is what the difference is with tree traversal. Since trees are acyclic we are never going to visit a node a second time. Thus, we don’t need to maintain a visited array.

We just need to ensure to avoid visiting the parent of the node. For this, we need to pass in the parent while doing DFS.

</aside>

Working

Edge Traversal