Skip to main content
Back to ChallengesDepth First Search (DFS)Easy 20 min

Depth First Search (DFS)

Given a graph as an adjacency list and a starting vertex, return the order of vertices visited using **Depth First Search**.

Visit neighbors in the order they appear in the adjacency list.

Examples

Input: graph = [[1,2],[0,3],[0,3],[1,2]], start = 0
Output: [0,1,3,2]
From 0, visit 1, then 1's unvisited neighbor 3, then backtrack to visit 2.
Input: graph = [[1],[0]], start = 0
Output: [0,1]
Simple two-node graph.

Constraints

  • • 1 <= vertices <= 1000
  • • Graph may be disconnected (only traverse reachable nodes)

Complexity Analysis

Time
O(V + E)
every vertex and edge visited once.
Space
O(V)
visited set and recursion/explicit stack.

Test Cases

#1 — Standard graph
Input: graph=[[1,2],[0,3],[0,3],[1,2]] start=0
Expected: [0,1,3,2]
#2 — Two-node graph
Input: graph=[[1],[0]] start=0
Expected: [0,1]
#3 — Isolated vertex
Input: graph=[[],[]] start=0
Expected: [0]

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.

Output
Click "Run Code" to see output here...