Breadth-First Search Traversal | Dataford Interview Questions

HP IQ can represent connected device relationships as a directed graph. Given an adjacency-list graph and a starting vertex, implement breadth-first search and return the order in which reachable vertices are visited.

Visit each vertex at most once. When processing a vertex, examine its neighbors in the order provided by the adjacency list. If multiple vertices are queued, process them FIFO. Return an empty list when start is not present in the graph.

Formal Specification

Implement bfs_traversal(graph, start), where graph is a dictionary mapping each vertex to a list of neighboring vertices, and start is a vertex identifier. Return a list containing the reachable vertex identifiers in BFS order. Vertices are represented by strings, and every neighboring vertex appears as a key in graph.

Constraints

1 <= len(graph) <= 10^5
The total number of adjacency entries is at most 2 * 10^5
Each vertex identifier is a non-empty string
Neighbor order must be preserved
The graph may contain cycles and may be disconnected

Function Signature

def bfs_traversal(graph, start):

Your question is Breadth-First Search Traversal. Start with the requirements in the Question tab.

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

Problem

Formal Specification

Constraints

1 <= len(graph) <= 10^5
The total number of adjacency entries is at most 2 * 10^5
Each vertex identifier is a non-empty string
Neighbor order must be preserved
The graph may contain cycles and may be disconnected

Function Signature

def bfs_traversal(graph, start):

Your question is Breadth-First Search Traversal. Start with the requirements in the Question tab.

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