Graph Depth First Traversal Order — Problem Statement & Solution Guide
Problem Description
You are provided with an undirected graph represented as an adjacency list, where the i-th element in the list contains the indices of all nodes directly connected to node i. Your task is to implement a function that performs a Depth-First Search (DFS) starting from a specified source node and returns the sequence of node indices in the exact order they are first visited.
The traversal must adhere to the standard DFS protocol: when at a current node, you must explore its unvisited neighbors in ascending numerical order of their indices. If a neighbor has already been visited, it is skipped. The process continues recursively or iteratively until all reachable nodes from the source have been processed. If the graph is disconnected, only the connected component containing the source node should be included in the result.
The function should accept two arguments: the adjacency list representing the graph and the integer index of the starting node. It must return a list of integers representing the traversal order.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Graph Depth First Traversal Order"
WHY DOES IT MATTER?
DFS is the foundational pattern for exploring connected components, detecting cycles, and solving problems that require backtracking. It is essential for understanding more complex algorithms like Tarjan's SCC, Kosaraju's algorithm, and topological sorting. Mastering DFS ensures you can handle any graph traversal problem with confidence.
OPTIMIZATION CHALLENGE
The key optimization is using an explicit stack instead of recursion to avoid stack overflow in deep graphs. Additionally, using a hash set for visited nodes instead of an array can be more memory-efficient for sparse graphs with large node indices.
REAL-WORLD CONNECTION
DFS is analogous to a human exploring a maze. You pick a path and go as deep as possible. If you hit a dead end, you backtrack to the last junction and try a different path. This is exactly how DFS works: it commits to a path until it can't go further, then backtracks to explore alternatives.
Always clarify the order of neighbor processing. If the problem requires a specific order (e.g., lexicographical), you must sort the adjacency list or use a priority queue. In interviews, explicitly state your assumption about neighbor order to avoid ambiguity.
COMPLEXITY AT A GLANCE
O(V + E)O(V)Core Theory — Why This Approach?
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. Unlike Breadth-First Search (BFS), which uses a queue to explore nodes level-by-level, DFS utilizes a stack (either explicitly or implicitly via recursion) to maintain the path of exploration. In the context of an undirected graph, the critical challenge is preventing infinite loops caused by revisiting nodes. Since edges are bidirectional, a naive traversal that does not track visited states will oscillate between two connected nodes indefinitely. Therefore, the core theoretical requirement is maintaining a 'visited' set or boolean array to mark nodes as soon as they are discovered, ensuring each node is processed exactly once.
The choice between recursive and iterative DFS is often a point of contention in large-scale systems. Recursive DFS is elegant and concise, leveraging the call stack to manage state. However, for graphs with high depth (long chains), recursive implementations risk stack overflow errors, which are catastrophic in production environments. Iterative DFS, using an explicit stack, offers better control over memory and allows for early termination or state modification without the overhead of function call frames. For large inputs, the iterative approach is generally preferred in engineering interviews and production code due to its predictability and safety.
The time complexity of DFS is linear with respect to the number of vertices and edges, O(V + E), because each node is visited once and each edge is examined at most twice (once from each endpoint in an undirected graph). The space complexity is O(V) for the visited array and the stack (in the worst case, where the graph is a single long path). This linear complexity makes DFS optimal for connectivity checks, cycle detection, and topological sorting in directed acyclic graphs (DAGs). Understanding the exact order of visitation is crucial, as it depends on the order in which neighbors are processed (e.g., ascending index order), which is often a specific requirement in coding challenges to ensure deterministic output.
Interview Questions on This Problem
Q1At a fintech platform like Stripe, we need to detect circular dependencies in a payment processing pipeline. How would you adapt a standard DFS to detect cycles in a directed graph, and how does this differ from an undirected graph?
In a directed graph, a cycle exists if we encounter a node that is currently in the recursion stack (or the current path) but has not been fully processed. We use three states: 'unvisited', 'visiting' (in current stack), and 'visited'. If we encounter a 'visiting' node, a cycle is detected. In an undirected graph, a cycle is detected if we encounter a visited node that is not the parent of the current node. The key difference is that in undirected graphs, back-edges to the parent are expected and do not indicate a cycle, whereas in directed graphs, any back-edge indicates a cycle.
Q2You are building a social network feature at a high-growth startup like LinkedIn. How would you use DFS to find all friends-of-friends (2nd degree connections) without traversing the entire graph, and what is the complexity?
You can modify DFS to stop after exploring two levels of depth. You pass a 'depth' parameter to the DFS function. If depth exceeds 2, you return immediately. This prunes the search space significantly. The time complexity becomes O(V + E) in the worst case if the graph is dense, but in practice, it is bounded by the number of nodes within 2 hops. The space complexity is O(V) for the visited set and the stack. This approach is efficient for small-world networks where the diameter is small.
Q3In a distributed system like AWS, how would you handle a graph traversal if the graph is too large to fit in memory, and how does DFS compare to BFS in this scenario?
If the graph is too large for memory, you cannot load the entire adjacency list. You would need to use external memory or a distributed graph database. DFS is often preferred over BFS in such scenarios because DFS requires less memory for the frontier (stack vs. queue) in many sparse graphs, although the worst-case space is still O(V). However, in distributed systems, BFS is often used for shortest path calculations, while DFS is used for connectivity or cycle detection. The key is to partition the graph and use a distributed coordination mechanism to track visited nodes across partitions.
Examples
Input
adjList = [[1, 2], [0, 3], [0, 4], [1, 4], [2, 3]], start = 0
Output
[0, 1, 3, 4, 2]
Explanation: Start at node 0. Visit 0. Neighbors of 0 are [1, 2]. Visit smallest unvisited neighbor 1. Visit 1. Neighbors of 1 are [0, 3]. 0 is visited, so visit 3. Visit 3. Neighbors of 3 are [1, 4]. 1 is visited, so visit 4. Visit 4. Neighbors of 4 are [2, 3]. 3 is visited, so visit 2. Visit 2. Neighbors of 2 are [0, 4]. Both are visited. Traversal complete. Order: 0, 1, 3, 4, 2.
Input
adjList = [[1, 3], [0, 2], [1, 4], [0, 4], [2, 3]], start = 2
Output
[2, 1, 0, 3, 4]
Explanation: Start at node 2. Visit 2. Neighbors of 2 are [1, 4]. Visit smallest unvisited neighbor 1. Visit 1. Neighbors of 1 are [0, 2]. 2 is visited, so visit 0. Visit 0. Neighbors of 0 are [1, 3]. 1 is visited, so visit 3. Visit 3. Neighbors of 3 are [0, 4]. 0 is visited, so visit 4. Visit 4. Neighbors of 4 are [2, 3]. Both are visited. Traversal complete. Order: 2, 1, 0, 3, 4.
Input
adjList = [[], [2], [1], [4], [3]], start = 0
Output
[0]
Explanation: Start at node 0. Visit 0. Node 0 has no neighbors (empty list). The traversal ends immediately as there are no other reachable nodes. Order: 0.
Input
adjList = [[1], [0, 2], [1, 3], [2, 4], [3]], start = 4
Output
[4, 3, 2, 1, 0]
Explanation: Start at node 4. Visit 4. Neighbors of 4 are [3]. Visit 3. Visit 3. Neighbors of 3 are [2, 4]. 4 is visited, so visit 2. Visit 2. Neighbors of 2 are [1, 3]. 3 is visited, so visit 1. Visit 1. Neighbors of 1 are [0, 2]. 2 is visited, so visit 0. Visit 0. Neighbors of 0 are [1]. 1 is visited. Traversal complete. Order: 4, 3, 2, 1, 0.
Constraints
- 1 <= adjList.length <= 10^4
- 0 <= start < adjList.length
- 0 <= adjList[i][j] < adjList.length
- The graph is undirected, meaning if j is in adjList[i], then i is in adjList[j].
- The graph may contain self-loops or multiple edges, but the adjacency list will not contain duplicate neighbors for a single node.
Optimal Approach & Strategy
Use an iterative DFS with an explicit stack and a visited set. Mark nodes as visited when they are pushed onto the stack (or popped, depending on the required order). Push neighbors in the correct order to ensure the desired visitation sequence. This avoids recursion overhead and ensures linear time complexity.
Brute Force Approach
A naive approach would be to recursively visit all neighbors without tracking visited nodes, which leads to infinite loops in undirected graphs. Alternatively, one might use BFS and then sort the result, but this does not produce the DFS order and is inefficient for this specific problem.
Verified Code Solutions
function solution(graph) {
const visited = new Set();
const order = [];
function dfs(node) {
visited.add(node);
order.push(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfs(neighbor);
}
}
}
for (let i = 0; i < graph.length; i++) {
if (!visited.has(i)) {
dfs(i);
}
}
return order;
}class Solution {
public:
vector<int> solution(vector<vector<int>>& graph) {
vector<bool> visited(graph.size());
vector<int> order;
function<void(int)> dfs = [&](int node) {
visited[node] = true;
order.push_back(node);
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor);
}
}
};
for (int i = 0; i < graph.size(); i++) {
if (!visited[i]) {
dfs(i);
}
}
return order;
};
}class Solution {
public int[] solution(int[][] graph) {
boolean[] visited = new boolean[graph.length];
int[] order = new int[graph.length];
int index = 0;
for (int i = 0; i < graph.length; i++) {
if (!visited[i]) {
dfs(graph, i, visited, order, index);
index++;
}
}
return Arrays.copyOfRange(order, 0, index);
}
private void dfs(int[][] graph, int node, boolean[] visited, int[] order, int index) {
visited[node] = true;
order[index] = node;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(graph, neighbor, visited, order, index);
}
}
}
}def solution(graph):
visited = set()
order = []
def dfs(node):
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
for i in range(len(graph)):
if i not in visited:
dfs(i)
return orderfunction solution(graph) {
const visited = new Set();
const order = [];
function dfs(node) {
visited.add(node);
order.push(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfs(neighbor);
}
}
}
for (let i = 0; i < graph.length; i++) {
if (!visited.has(i)) {
dfs(i);
}
}
return order;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.