DFS Runtime and Space on Graph Representations

Why the Representation Matters

Depth-first search (DFS) follows a path as far as possible before returning to explore another choice. The traversal rule is the same whether a graph is stored as adjacency lists or as an adjacency matrix, but the work needed to find each vertex’s neighbors differs. With lists, DFS scans the neighbors that are actually present. With a matrix, it checks every possible neighbor, including non-neighbors. These differences determine the running time.

We analyze a full DFS forest: the algorithm starts at a chosen root, and then starts again from each vertex not yet visited. This second step matters for disconnected graphs. Unless stated otherwise, the graphs in the examples are finite, simple, and directed. An edge \(uv\) means the directed edge from \(u\) to \(v\); the adjacency list of \(u\) contains its outgoing neighbors. For an undirected graph, each edge appears in two adjacency lists, which changes list-scan counts by a factor of two but not the asymptotic bounds.

For implementation details, assume each list entry or matrix entry can be read in constant time. A recursive DFS keeps a call active while it explores a newly discovered neighbor. An equivalent iterative implementation can use an explicit stack of frames: each frame records a vertex and which neighbor is next to examine. This frame-based implementation preserves the recursive traversal order. We count the graph representation as input storage, not auxiliary space; traversal state such as visited marks, parent pointers, and stack frames is auxiliary space. If the DFS outputs a parent forest, its \(O(n)\) storage does not change the bounds below.

The Time Bounds

Proof. First consider adjacency lists. Initializing a visited mark for each vertex takes \(O(n)\) operations, and the loop that checks whether each vertex needs to start a new search also takes \(O(n)\). Every time DFS processes a vertex, it scans that vertex’s entire list. Across the full forest, each directed edge occurs in exactly one such list, so the total number of list entries scanned is \(m\). The total work is therefore \(O(n+m)\). It is also at least proportional to \(n+m\): the algorithm initializes and checks all \(n\) vertices, and a full traversal scans all \(m\) list entries. Thus the time is \(\Theta(n+m)\).

For an adjacency matrix, a processed vertex requires scanning its entire row of \(n\) entries. Every vertex is eventually processed, including isolated vertices and vertices in components reached by later roots. The row scans therefore total \(n\cdot n=n^2\). Initialization and the root loop take \(O(n)\), which is bounded by \(O(n^2)\) for \(n\ge1\). Hence the total time is \(\Theta(n^2)\). If \(n=0\), there are no vertices or rows to process; the stated asymptotic bounds describe the usual nonempty input sizes. \(\square\)

The list bound includes both the cost of looking for undiscovered components and the work of scanning edges. It does not become \(O(m)\) when the graph is sparse: an edgeless graph still has \(n\) vertices to initialize and check. Conversely, the matrix bound remains quadratic even when very few entries are \(1\), because DFS does not know which entries are \(1\) without checking the row.

Stack Space and Disconnected Components

DFS also needs to remember which vertices have been visited. A visited array uses \(O(n)\) space. If parent pointers, colors, or discovery and finishing times are stored, each contributes at most a constant amount of data per vertex and therefore uses \(O(n)\) space. These arrays are auxiliary state, not part of the input graph representation.

In recursive DFS, each active call corresponds to a vertex on the current search path. A vertex is marked when discovered, so it cannot be discovered again and added as a second active call. There are at most \(n\) distinct vertices, and hence at most \(n\) active calls. The recursion stack is \(O(n)\) in the worst case. A chain of \(n\) vertices can attain depth \(n\), so the bound is tight.

An explicit stack of frames has the same \(O(n)\) worst-case bound when it simulates recursive DFS: each active frame corresponds to a discovered vertex whose neighbor scan has not finished. A frame needs only a vertex identifier and a position in that vertex’s neighbor list (or row). The number of active frames is at most \(n\). This is different from implementations that push many neighbors at once; their stack contents and traversal order depend on when vertices are marked and how duplicate entries are handled. For the recursive semantics considered here, use frames that retain the current neighbor position.

Proof. The visited array has one entry per vertex, and any parent or other per-vertex traversal data has at most one entry per vertex. These arrays use \(O(n)\) space. At any moment, active recursive calls—or their explicit-frame equivalents—correspond to distinct discovered vertices: DFS marks each vertex on discovery, and a marked vertex is not discovered again. Thus there are at most \(n\) active calls or frames, using \(O(n)\) additional space. A directed path on \(n\) vertices, with its first vertex as the root, can require all \(n\) vertices to be active before the deepest call finishes. Therefore the worst-case stack space is \(\Theta(n)\). When a component finishes, its calls or frames are removed before a new root is explored; disconnected components do not add their stack depths together. \(\square\)

Common Runtime and Space Mistakes

Mistake: counting matrix work only where edges exist. In the four-vertex example, it would be wrong to say DFS checks only the two \(1\) entries and therefore takes \(O(m)\) matrix work. The correction is to count every entry in each processed row: four rows times four entries per row gives \(16\) checks, even though the graph has only two edges.

Mistake: ignoring isolated vertices. If a list-based analysis reports only \(m\) work, it omits initialization and the loop that finds new roots. In the seven-vertex example, the isolated vertices \(6\) and \(7\) contribute no adjacency entries, but DFS still initializes and checks them. The correct bound includes \(n\), giving \(\Theta(n+m)\).

Mistake: adding stack depths across components. DFS explores components sequentially. Once one component finishes, its active calls have returned or its frames have been popped. Thus the maximum stack size is the largest active search depth at any one time, not the sum of the sizes of all components. The total traversal time, in contrast, includes work in every component.

These distinctions are useful when choosing a representation. For sparse graphs, adjacency lists avoid scanning absent edges and yield a linear-in-input-size DFS bound. Matrices provide constant-time tests for a particular ordered pair but require a full row scan during standard DFS. Either representation uses \(O(n)\) auxiliary traversal space with recursive-style DFS; the input storage itself is separate and depends on the chosen representation.