Implement BFS Algorithm | Dataford Interview Questions

Your question is Implement BFS Algorithm. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

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):