BFS Implementation

The Nio Robotics navigation stack represents reachable rover locations as a directed graph. Given an adjacency-list graph and a starting location, implement breadth-first search (BFS) and return the order in which locations are visited.

Visit each reachable location at most once. When processing a location, examine its neighbors in the order listed in the adjacency list. If multiple locations are discovered at the same BFS distance, preserve the discovery order created by that neighbor ordering. Ignore locations that are not reachable from start.

Formal Specification

Implement bfs_traversal(graph, start).

• graph is a dictionary mapping a node identifier to a list of neighboring node identifiers.
• start is a node identifier present in graph.
• Return a list containing the BFS visitation order.
• The graph may contain cycles and self-loops.
• The graph is directed. An edge exists from node u to every node in graph[u].