BFS Level Counts

Problem

Count how many nodes sit at each BFS distance from a source.

edges is an undirected edge list and start is the source node. Return a list whose index d holds the number of nodes at distance d from start, beginning with the source at index 0. Nodes in other components are unreachable and are not counted.

Hint

First compute every distance with BFS, then bin the visited nodes by distance.

Test cases

case 1

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

expected: [1,2,1]

case 2

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

expected: [1,1]

case 3

in: [3,[],2]

expected: [1]

case 4

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

expected: [1,1,1]

Starter codePython

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

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