DFS Traversal Order (Iterative)

Problem

Return the order in which nodes are visited by an iterative depth-first traversal starting at start, visiting the smallest neighbor first.

The graph is undirected with n nodes. Implement the stack yourself (no recursion) and skip unreachable nodes.

Hint

Push neighbors in reverse sorted order so the smallest one is popped first.

case 1

in: [5,[[0,1],[0,2],[1,3],[2,4]],0]

expected: [0,1,3,2,4]

case 2

in: [5,[[0,1],[0,2],[1,3],[2,4]],2]

expected: [2,0,1,3,4]

case 3

in: [4,[[0,1],[1,2],[2,0],[1,3]],0]

expected: [0,1,2,3]

case 4

in: [2,[],1]

expected: [1]

Starter codePython

def dfs_order(n, edges, start):
    # Your code here
    pass

4 test cases · run your code against them in the editor