Breadth-First Order of a Graph
Updated
Problem statement
An undirected graph has n nodes numbered 0 to n - 1. It is given as adjacency lists: adj[i] lists the neighbours of node i.
Return the order in which a breadth-first search visits the nodes when it starts at node 0:
- Visit node
0first. - Nodes are visited in the order they are first discovered. When a node is visited, its neighbours that have not been discovered yet are discovered in the order they appear in its list.
- So all nodes one edge away from node
0come before all nodes two edges away, and so on.
Nodes that cannot be reached from node 0 are not part of the answer.
Function
bfsOrder(adj: int[][]) → List<Integer>Examples
Example 1
adj = [[2,1],[0,3],[0,4,3],[1,2],[2],[]]return = [0,2,1,4,3]Start at 0 and queue its neighbours in list order: 2, then 1. Visiting 2 queues 4 and 3 (0 is already seen). Visiting 1 adds nothing new, because 0 and 3 are already seen. Then 4 and 3 are visited. Node 5 has no edges and is never reached. Order: [0,2,1,4,3].
Example 2
adj = [[]]return = [0]One node and no edges: only node 0 is visited.
Example 3
adj = [[1,4],[0,2],[1,3],[2,4],[3,0]]return = [0,1,4,2,3]The nodes form a ring 0-1-2-3-4-0. Both neighbours of 0 (1, then 4) are one step away, so they come right after 0; then 2 (found from 1) and 3 (found from 4). Order: [0,1,4,2,3]. A depth-first walk would give 0, 1, 2, 3, 4 instead.
Constraints
1 <= n == adj.length <= 20000 <= adj[i][j] < n- The lists hold at most 8000 numbers in total (at most 4000 edges)
- The graph is undirected:
jis inadj[i]exactly wheniis inadj[j]. No node lists itself, and no list repeats a node
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Crawl Reachable Pages with Bounded RetriesSnowflake · PHONE SCREENSnowflake interview questions
- Shortest Path in an Unweighted GraphCitadel · OACitadel interview questions
- Distances to CyclesBelvedere Trading · OA
- Cogwheel Rotation DirectionsOpenAI · OAOpenAI interview questions
- Path Existence in an Undirected GraphByteDance · PHONE SCREENByteDance interview questions
- Number of IslandsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Word Chain Jumps in a GridGoogle · PHONE SCREENGoogle interview questions
- Linked Merchants Within Two HopsStripe · PHONE SCREENStripe interview questions
- Bus RoutesUiPath · PHONE SCREEN
- Evaluate DivisionApple · PHONE SCREENApple interview questions