Implement BFS Algorithm

EasyPython

Problem

Seagate Lyve Mobile devices can be modeled as vertices in a directed connectivity graph. Given an adjacency-list representation and a starting device, return the order in which devices are visited using breadth-first search (BFS).

Visit each reachable device at most once. When processing a device, examine its neighbors in the order provided by the adjacency list. Mark a device visited when it is added to the queue, not when it is removed. Return an empty list if start is not present in graph.

Formal Specification

Implement bfs_traversal(graph, start):

graph is a dictionary mapping string device identifiers to lists of string neighbor identifiers.
start is a string identifying the first device.
Return a list of strings containing the BFS traversal of all devices reachable from start.
The graph may contain cycles and self-loops. It is directed, so an edge from A to B does not imply an edge from B to A.

Constraints

0 <= number of vertices <= 10^5
0 <= number of directed edges <= 2 * 10^5
Each vertex identifier is a non-empty string
Every neighbor identifier appears as a key in graph
Neighbor lists preserve the required traversal order

Function Signature

def bfs_traversal(graph, start):

Formal Specification

Implement bfs_traversal(graph, start):

graph is a dictionary mapping string device identifiers to lists of string neighbor identifiers.
start is a string identifying the first device.
Return a list of strings containing the BFS traversal of all devices reachable from start.
The graph may contain cycles and self-loops. It is directed, so an edge from A to B does not imply an edge from B to A.