Depth-First Search Traversal | Dataford Interview Questions

An HP IQ graph-processing component represents a directed graph as an adjacency list. Given the graph and a starting node, return the nodes visited by a depth-first search, preserving the order of neighbors in the adjacency list.

The graph may contain cycles. Visit each reachable node at most once, and do not include nodes that cannot be reached from start. Use an iterative implementation with an explicit stack.

Formal Specification

Implement dfs_traversal(graph, start), where graph is a list of lists. graph[u] contains the integer IDs of nodes directly reachable from node u, and valid node IDs range from 0 through len(graph) - 1. Return a list of node IDs in DFS preorder. When multiple unvisited neighbors are available, process them in the order listed in graph[u].

Constraints

1 <= len(graph) <= 10^5
0 <= start < len(graph)
Every neighbor ID is between 0 and len(graph) - 1
The total number of adjacency entries is at most 2 * 10^5

Function Signature

def dfs_traversal(graph, start):

Your question is Depth-First Search Traversal. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem