182. DFS Traversal of a Graph

Given an undirected graph with n vertices (0-indexed) and m edges, and a starting vertex, print its depth-first traversal order starting from that vertex, space-separated. When multiple unvisited neighbors are available, visit them in ascending order of vertex number. Only vertices reachable from the start should appear.

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges. Each of the next m lines contains two space-separated integers u and v, an undirected edge. The final line contains the starting vertex. Output: Print the DFS traversal order starting from the given vertex, space-separated.

1 <= n <= 10^5

DFS and BFS both visit the same set of REACHABLE vertices, but in genuinely different ORDERS - recognizing which order a specific problem needs (level-by-level for shortest paths, versus deep-then-backtrack for things like cycle detection or topological sort) is a key skill.

Visit every reachable vertex of a graph by fully exploring one path before backtracking to try another. Brute force: There isn't a meaningfully different 'slower' approach - recursive (or explicit-stack-based) DFS IS the standard, direct way to achieve depth-first graph traversal. Optimised: Marking a vertex visited as soon as it's first reached (whether via recursion or an explicit stack) is what prevents infinite loops on graphs containing cycles - without this tracking, DFS could recurse forever bouncing between connected vertices.

Build an adjacency list from the edge list and sort each vertex's neighbor list once so neighbors are visited in ascending order, then perform the same recursive DFS as before. Because the DFS now only looks at a vertex's actual neighbors instead of scanning every other vertex, the traversal cost drops to be proportional to the number of edges rather than n^2, with the one-time sorting adding a log factor on top. The only remaining downside is that recursion depth can reach n for a long chain, risking a stack overflow for large inputs. Time: O((n+m) log m) Space: O(n+m)

Represent the graph as an n x n adjacency matrix built from the edge list, then run a standard recursive DFS from the start vertex: at each visited vertex, scan the entire matrix row to find unvisited neighbors in ascending order and recurse into each. Building and scanning the matrix costs O(n) per vertex regardless of how many actual edges exist, so for sparse graphs this does far more work than necessary, and the matrix itself needs quadratic memory. Time: O(n^2) Space: O(n^2)

Keep the sorted adjacency list from the better approach, but replace the recursive call with an explicit stack that is manually managed: push a vertex's unvisited neighbors in descending order so that popping them off yields ascending order, mark vertices visited as they're popped (not just pushed) to guarantee correctness even with duplicate stack entries, and continue until the stack empties. This preserves the same near-linear time complexity as the recursive version but removes any dependency on the language's call stack, which matters here since n can be up to 10^5 and a skewed graph could otherwise crash a recursive solution with a stack overflow. Time: O((n+m) log m) Space: O(n+m)

1. Recursively visit the CURRENT vertex, then recurse into its SMALLEST unvisited neighbor first. 2. Continue fully exploring that branch (going as deep as possible) before returning to try the current vertex's next neighbor. 3. Mark each vertex visited the moment you first visit it, to avoid infinite loops on graphs with cycles.

Time: O(n + m) - every vertex is visited once, and every edge is examined once. Space: O(n) for the recursion stack in the worst case (a long chain-like graph), plus O(n) for the visited tracking.

a start vertex with no edges, vertices unreachable from the start that must be excluded from output, and n at its upper bound of 10^5 to confirm the traversal runs efficiently.

Be ready to implement BOTH the recursive version (natural, but risks stack overflow on very deep/large graphs) and an iterative version using an explicit stack - interviewers often specifically ask for the iterative one to test comfort with explicit stack management.