Graph BFS Traversal

Problem

Return the order in which nodes are visited by a breadth-first traversal of adj starting at start, visiting neighbours in the order they appear in each adjacency list.

Use a queue and a visited set, appending a node when it is first discovered. Only nodes reachable from start appear in the result.

Hint

Mark nodes when you enqueue them, not when you dequeue, so they are never queued twice.

Test cases

case 1

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

expected: [0,1,2,3]

case 2

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

expected: [0,1,2]

case 3

in: [[[]],0]

expected: [0]

case 4

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

expected: [0,1,2]

case 5

in: [[[1],[0]],0]

expected: [0,1]

Starter codePython

def bfs_order(adj, start):
    # Your code here
    pass

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