Given an undirected graph with V vertices (labelled 0 .. V-1) and an edge list edges, return its BFS and DFS traversals as a two-row array: row 0 is the breadth-first order, row 1 is the depth-first order.
Start both from vertex 0 and, at every vertex, visit its neighbours in increasing order. If the graph is disconnected, continue from the smallest unvisited vertex so every vertex appears.
Input: V = 5, edges = [[0,1],[0,2],[1,3],[2,4]] Output: [[0,1,2,3,4],[0,1,3,2,4]] BFS explores in rings from 0; DFS goes deep down 0-1-3 then 0-2-4.
Input: V = 5, edges = [[0,1],[2,3]]
Output: [[0,1,2,3,4],[0,1,2,3,4]]
Disconnected: after component {0,1}, restart at 2, then the isolated 4.- 1 <= V <= 10^4 - 0 <= edges.length <= V*(V-1)/2 - 0 <= u, v < V - u != v - no duplicate edges
Every graph algorithm starts by building an adjacency list and then walking it one of two ways.
BFS (breadth-first) uses a queue and explores in rings — all vertices one edge away, then two, and so on. Mark a vertex visited when you enqueue it so it's never queued twice. On an unweighted graph BFS also gives shortest paths.
DFS (depth-first) goes deep — follow an edge as far as it leads, then backtrack — via recursion or an explicit stack. The recursive and iterative forms produce the same order if the iterative one pushes neighbours in reverse (so the smallest is popped first) and marks a vertex visited when it's popped.
Sorting each adjacency list makes both traversals deterministic (ties broken by smallest label), and looping the start over every vertex handles disconnected graphs. Both are O(V + E).
“In what order are neighbours visited?”
Ascending by label, so the traversal is unique.
“What about disconnected graphs?”
Restart from the smallest unvisited vertex until all are covered.
I build a sorted adjacency list, then BFS with a queue and DFS with recursion, marking visited to avoid cycles.
Looping the start over unvisited vertices covers disconnected components; both walks are O(V+E).
Worked example — V = 5, edges [[0,1],[0,2],[1,3],[2,4]]
BFS from 0: 0, then 1,2, then 3,4 -> [0, 1, 2, 3, 4] DFS from 0: 0 -> 1 -> 3 (back) -> 2 -> 4 -> [0, 1, 3, 2, 4]
Almost every graph algorithm converts the edge list to adjacency before walking.
The container choice is the only structural difference between them.
Covers disconnected graphs; each vertex is processed exactly once.
| Recursive DFS | Iterative DFS | |
|---|---|---|
| DFS via | the call stack | an explicit stack (push neighbours reversed) |
| Order | same preorder | same preorder |
| Space | O(V) recursion | O(V) explicit |
BFS is identical in both; only the DFS implementation differs. Full code is in the Approaches selector below.
Key takeaway
Build a sorted adjacency list, then BFS with a queue and DFS with recursion (or an explicit stack pushing neighbours reversed). A visited array prevents cycles; restarting on unvisited vertices covers disconnected graphs. O(V+E).
bfs: queue, mark-on-enqueue dfs: recurse / stack, mark-on-visit restart from each unvisited vertex