Graph Traversal Coding Problem | Dataford Interview Questions

Given a graph traversal type question, how would you approach solving it?

Implement breadth-first search for a directed graph represented by an adjacency-list dictionary. Starting from start, return the nodes in the order BFS visits them. Mark nodes when enqueued so cycles do not cause repeated visits. Preserve the neighbor order provided in each adjacency list.

Input: graph is a dictionary from node labels to lists of neighboring labels, and start is a node in graph. Output: a list of visited node labels. Assume every referenced neighbor appears as a key.

Examples: {"A":["B","C"],"B":["D"],"C":[],"D":[]}, "A" returns ["A","B","C","D"]; {"A":["B"],"B":["A"]}, "A" returns ["A","B"].

Constraints: up to 10^5 nodes and 2 * 10^5 directed edges; labels are hashable; the graph may contain cycles and disconnected components.

Constraints

1 <= number of nodes <= 10^5
0 <= number of directed edges <= 2 * 10^5
Every neighbor referenced in an adjacency list is a key in graph
Node labels are hashable
The graph may contain cycles and disconnected components

Function Signature

def bfs_traversal(graph, start):

Your question is Graph Traversal Coding Problem. 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