Temporal Snapshot BFS

Problem

Compute which nodes are reachable in a temporal graph given as a list of snapshots.

Start at node src at time 0. For each of the first t snapshots in order, all edges of that snapshot can be traversed simultaneously; a node reached at time i may use snapshot i+1 next. Return the sorted list of nodes reachable by time t. snapshots is a list of edge lists.

Hint

Time only moves forward, so a snapshot that has passed cannot be used later.

Test cases

case 1

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

expected: [0,1,2,3]

case 2

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

expected: [0,1]

case 3

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

expected: [0,1,2]

case 4

in: [3,[],1,5]

expected: [1]

case 5

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

expected: [0]

Starter codePython

def temporal_bfs(n, snapshots, src, t):
    # Your code here
    pass

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