Iterative Depth-First Search
Meta● MediumFULLTIMEONSITE INTERVIEWProblem statement
You are given a directed graph as an adjacency list adjacency and a starting vertex start. Vertices are numbered from 0 through adjacency.length - 1. Each neighbor list is ordered.
Implement depth-first search iteratively, without recursive calls. Visit neighbors in their listed order, and append a vertex to the result when it is first visited. Return that preorder of the vertices reachable from start. Visit each vertex only once, even when the graph has cycles, self-loops, or repeated edges. Do not include unreachable vertices.
Function
iterativeDfs(adjacency: int[][], start: int) → int[]Examples
Example 1
adjacency = [[1,2],[2,3],[3],[]]start = 0return = [0,1,2,3]Visit 0, then follow its first neighbor 1. From 1, visit 2, then 3. Later edges to already visited vertices add nothing.
Example 2
adjacency = [[2,1],[3],[3],[1],[]]start = 0return = [0,2,3,1]The first listed neighbor of 0 is 2. Continue through 3 and 1; the edge from 1 back to 3 is skipped. Vertex 4 is unreachable.
Example 3
adjacency = [[],[0],[1]]start = 2return = [2,1,0]From start vertex 2, the only path is 2 → 1 → 0.
Constraints
1 <= adjacency.length <= 100000.0 <= start < adjacency.length.- Every neighbor is a valid vertex number. The graph may contain cycles, self-loops, and repeated edges.
- The sum of all neighbor-list lengths is at most
200000.