Trace All Paths in a Directed Graph: DFS with Backtracking

Tracing all paths between two nodes in a directed graph is a depth-first search problem solved with backtracking, not plain DFS.

Standard depth-first search marks each node visited and skips it on future visits. That works when you want to know whether a path exists. It fails when you need every distinct path, because different paths often share intermediate nodes. Backtracking fixes this by unmarking a node after recursion returns, allowing the same node to appear across separate paths.

What the Problem Asks

Given a directed graph as an adjacency list and two nodes, a source and a destination, find and print every simple path from source to destination. A simple path does not repeat any vertex.

Consider this five-node directed graph:

Source vertex	Outgoing neighbors
0	1, 2
1	3
2	3
3	4
4	(none)

With source = 0 and destination = 4, there are two valid paths:

• 0 → 1 → 3 → 4
• 0 → 2 → 3 → 4

Both pass through vertex 3, but each uses a different intermediate node (1 or 2). The algorithm must find both. Vertex 3 is reachable from two directions, so it appears in both paths, which is exactly what backtracking makes possible.

Depth-First Search with Backtracking

Plain DFS visits each node at most once per graph traversal. For shortest-path or reachability problems, that is correct behavior. For all-paths enumeration, it is the wrong choice: once node 3 is marked visited on the path through node 1, it is unavailable when the algorithm tries to reach node 4 via node 2.

The fix is a three-step cycle applied to every node.

Mark before recursing

Add the node to the current path list and set its visited flag to true. This prevents the current path from revisiting it, avoiding cycles within one path.

Check at the destination

When the current node equals the destination, record or print the current path. Then return. Do not stop the traversal. Other paths may still exist and will be found as the recursion unwinds.

Unmark after returning

After all recursive calls from a node return, remove it from the path list and set its visited flag to false. This is the backtracking step. It frees the node for inclusion in any other path that has not yet been explored.

The sequence is: mark, explore neighbors, unmark. The visited flag is path-local, not graph-global.

Python Implementation

The adjacency list is stored as a dictionary mapping each vertex to its list of outgoing neighbors. The inner dfs function uses a closure over the shared visited list and path list.

from collections import defaultdict

def find_all_paths(graph, n_vertices, source, destination):
    visited = [False] * n_vertices
    path = []

    def dfs(node):
        visited[node] = True
        path.append(node)

        if node == destination:
            print(" -> ".join(map(str, path)))
        else:
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    dfs(neighbor)

        path.pop()
        visited[node] = False

    dfs(source)


# Build the five-node example graph
graph = defaultdict(list)
for u, v in [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]:
    graph[u].append(v)

find_all_paths(graph, 5, 0, 4)

Output:

0 -> 1 -> 3 -> 4
0 -> 2 -> 3 -> 4

The path.pop() and visited[node] = False lines after the recursive calls are the backtracking steps. Remove either one and the function finds only one path. Remove path.pop() and the path list grows stale. Remove visited[node] = False and node 3 stays locked after the first path, blocking the second.

C Implementation

The C version uses an adjacency matrix. Entry adj[u][v] = 1 indicates a directed edge from u to v. The constant VCOUNT sets the number of vertices.

#include <stdio.h>
#include <stdbool.h>

#define VCOUNT 5

int adj[VCOUNT][VCOUNT] = {
    {0, 1, 1, 0, 0},
    {0, 0, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0}
};

bool visited[VCOUNT];
int path[VCOUNT];
int path_len = 0;

void dfs(int current, int destination) {
    visited[current] = true;
    path[path_len++] = current;

    if (current == destination) {
        for (int i = 0; i < path_len; i++) {
            if (i > 0) printf(" -> ");
            printf("%d", path[i]);
        }
        printf("\n");
    } else {
        for (int v = 0; v < VCOUNT; v++) {
            if (adj[current][v] && !visited[v]) {
                dfs(v, destination);
            }
        }
    }

    path_len--;
    visited[current] = false;
}

int main() {
    dfs(0, 4);
    return 0;
}

Output matches the Python version:

0 -> 1 -> 3 -> 4
0 -> 2 -> 3 -> 4

The adjacency matrix uses O(VCOUNT^2) memory for input storage. For sparse graphs with a large vertex count, the adjacency list (as used in the Python version) is more efficient at O(V + E) space.

Time and Space Complexity

Space analysis is straightforward: the three auxiliary structures are each bounded by the number of vertices.

Component	Space
visited array	O(V)
path / path_len array	O(V)
Recursion stack depth	O(V) (at most one frame per vertex on the current path)
Total auxiliary space	O(V)

The adjacency matrix in the C version adds O(V^2) for input representation. The adjacency list in the Python version adds O(V + E). Both are input storage, separate from auxiliary space.

Time complexity is harder to bound tightly. Unlike standard DFS, this algorithm revisits nodes across different path explorations because of backtracking. The total work is proportional to the sum of lengths of all distinct paths found. For a directed acyclic graph with few paths, that sum is small. For a graph structured to maximise path count, the runtime grows fast, reaching exponential in the worst case.

The GeeksforGeeks analysis of finding all paths given source and destination covers the worst-case derivation in detail. For placement interviews, the accepted answer is O(V) auxiliary space and exponential time in the worst case, with the note that real inputs rarely hit that ceiling.

For a broader look at how space complexity behaves across recursive algorithms and graph representations, space complexity of algorithms with examples is a useful companion.

Graph Problems in Placement Rounds

Graph traversal problems appear in coding rounds at TCS, Cognizant, Wipro, and product companies that hire from engineering colleges. The all-paths variant specifically tests whether candidates understand backtracking as a concept distinct from plain visited-flag DFS. In practice, many students who can solve standard BFS or DFS questions get this wrong by forgetting to unmark nodes after recursion.

When this question comes up in an interview, a complete answer covers three points: the algorithm (DFS with backtracking), the space complexity (O(V) auxiliary), and the note that time complexity is exponential in the worst case but tractable for sparse, acyclic graphs. Graph problems are also common in technical rounds at product companies like PayPal India, where the follow-up is often cycle detection (handled by maintaining a separate permanent visited array alongside the backtracking one).

The mark-explore-unmark pattern in this article is the same skeleton behind N-Queens, Sudoku solvers, and word-break problems. Building one of these into a working project, pushed to a public GitHub, turns a studied algorithm into demonstrated problem-solving ability. TinkerLLM provides a Python sandbox where you can run, iterate, and share exactly this kind of implementation at ₹499, without local environment setup.