PPractick

The problem

A social app shows "people you may know" by exploring the network outward in rings: first your direct friends, then their friends, and so on. That's breadth-first search. Starting from vertex 0, a queue holds discovered-but-unprocessed vertices. Each vertex is marked visited when it's enqueued, so it's never added twice, and neighbours are explored in the order they appear in the adjacency list. The visit order lists vertices by increasing distance from the start.

Example: adjacency [[1,2,3], [], [4], [], []] → [0, 1, 2, 3, 4].

Function signature

vector<int> bfsOfGraph(const vector<vector<int>>& adj);  // start at vertex 0

Test cases

Input (adjacency list)	Output	Explanation
[[1,2,3], [], [4], [], []]	[0, 1, 2, 3, 4]	4 is two steps away
[[1,2], [0,3], [0,3], [1,2]]	[0, 1, 2, 3]	A square: 3 is reached once
[[2], [2], [0,1]]	[0, 2, 1]
[[1], [0,2], [1]]	[0, 1, 2]	A path
[[]]	[0]

(Confirm: neighbours are explored in list order; only vertices reachable from 0 appear.)

How interviewers phrase it

• "Given a graph as an adjacency list, return its BFS traversal starting from vertex 0" (GeeksforGeeks "BFS of graph").

Clarifying questions to ask

1. Directed or undirected? (Either: BFS works the same.)
2. Should unreachable vertices be included? (No, only those reachable from 0.)
3. Does the neighbour order matter? (Yes, follow the list order.)

Follow-ups to expect

1. "Why mark visited when enqueuing, not when dequeuing?"
2. "What does BFS guarantee?"
3. "How do you cover disconnected graphs?"
4. "BFS vs DFS?"
5. "Complexity?"

Related questions

• Connected Components Medium
• Number of provinces Medium
• Connected Components Problem in Matrix Medium
• Flood fill algorithm Medium
• Surrounded Regions Medium
• Number of enclaves Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in