ML Prep

Compute unweighted distances with BFS

Problem

Implement bfs_distances(graph, start) for a directed unweighted graph represented by a dictionary from a node to its neighbors in deterministic list order. Return a dictionary mapping each reachable node to its minimum edge distance from start. A node mentioned only as a neighbor has no outgoing edges.

Reveal answer or reference solution

Enqueue the start at distance zero. The first time BFS discovers a node, assign its predecessor distance plus one and enqueue it. The distance dictionary also serves as the visited hash map. The complexity is O(V+E)O(V + E) time and O(V)O(V) auxiliary space over reachable nodes and edges.

from collections import deque
 
def bfs_distances(
    graph: dict[str, list[str]], start: str
) -> dict[str, int]:
    distances = {start: 0}
    frontier = deque([start])
    while frontier:
        node = frontier.popleft()
        neighbors = graph[node] if node in graph else []
        for neighbor in neighbors:
            if neighbor in distances:
                continue
            distances[neighbor] = distances[node] + 1
            frontier.append(neighbor)
    return distances

Public tests

  • bfs_distances({"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}, "A") → {'A': 0, 'B': 1, 'C': 1, 'D': 2}
  • bfs_distances({"A": ["B"], "B": ["A"], "X": []}, "A") → {'A': 0, 'B': 1}
  • bfs_distances({}, "Z") → {'Z': 0}
Outcome

Previous attempts

Loading attempts saved in this browser…

    Review Screening Results