Code it · Write it
Write breadth-first search
Write bfs_levels(graph, start) (Python) or bfsLevels(graph, start) (JavaScript/TypeScript). graph[u] lists the neighbours of node u (one-way graphs list only the edges leaving u), in alphabetical order.
Return a dict (an object in JavaScript) from every node start can reach to its level: the fewest edges on any path from start. Leave out nodes it can’t reach.
Use a queue. start is level 0. Take the node at the front, and give each neighbour you haven’t seen yet a level one higher, putting it at the back of the queue.
from collections import deque
def bfs_levels(graph, start):
# graph[u] lists u's neighbours. Return {node: level} for every node start reaches.
# deque([start]) is a queue: append() adds at the back, popleft() takes from the front.
level = {start: 0}
return level