Breadth-First Search

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Breadth-First Search. 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.

You need to log in / sign up to run or submit.

Problem

Implement breadth-first search on a graph and return the order in which nodes are visited starting from a given node.

The graph is represented as an adjacency list: a dictionary where each key is a node and its value is a list of neighboring nodes. Visit neighbors in the order they appear in the list. If the start node is not in the graph, return an empty list.

Formal Specification

Write a function bfs(graph, start) that returns a list of nodes in BFS visitation order.

graph: dict mapping each node to a list of adjacent nodes
start: the starting node
Return: list of nodes visited in BFS order

Use a queue for traversal and avoid visiting the same node more than once.

Constraints

0 <= len(graph) <= 10^4
Total number of edges across all adjacency lists is at most 10^5
Node values are hashable
The graph may contain cycles and disconnected components

Function Signature

def bfs(graph, start):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output