DFS Traversal
Practice this coding question on Coding Gurukul.
Problem statement
Given an undirected graph and a starting vertex s, print its Depth-First Search (DFS) preorder traversal. Print a vertex when it is first visited. Check its neighbors in increasing numeric order. Fully explore an unvisited neighbor before moving to the next neighbor. Visit each vertex once and include only vertices reachable from s. Self-loops and repeated edges must not cause repeated visits. Use an explicit stack to handle deep graphs. Worked example Start at 0, visit 1, and then visit 3 through 1. Return to 0 and visit 2. The order is 0 1 3 2. Vertex 4 is disconnected.
Input format
First line: n m s. Next m lines: undirected edge endpoints u v.
Output format
Print the traversal order as space-separated vertex numbers.
Constraints
1 <= n <= 100000; 0 <= m <= 200000; 0 <= s,u,v < n.
Sample input
5 3 0 0 2 1 3 0 1
Sample output
0 1 3 2
Sign in to run or submit a solution in C++, Java or Python.