BFS Distance Sum

Problem

Sum the BFS distances from a start node to every reachable node in an unweighted undirected graph.

edges is a list of [u, v] pairs and start is a single node. Distances already include the start itself at distance 0, which contributes nothing to the sum. Unreachable nodes are ignored, so return 0 when start is isolated.

Hint

Run a standard BFS, then add up the positive distances only.

Test cases

case 1

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

expected: 6

case 2

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

expected: 2

case 3

in: [3,[],1]

expected: 0

case 4

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

expected: 1

case 5

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

expected: 1

Starter codePython

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

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