Depth-First Search (DFS)
Last updated
Depth-first search explores a graph by going as deep as possible along each branch before backtracking. Starting from a source node, it visits a neighbor, then that neighbor's neighbor, and so on until it hits a dead end (a node with no unvisited neighbors), at which point it backtracks and tries the next branch. Press play above to watch it dive down one path, hit the bottom, and back out.
DFS is naturally expressed with a stack - either an explicit stack (as animated here) or the call stack via recursion. It visits every node and edge once, so it runs in O(V + E) time for a graph with V vertices and E edges.
Time & space complexity
| Measure | Complexity | Notes |
|---|---|---|
| Time | O(V + E) | Every vertex and edge visited once |
| Space | O(V) | Stack + visited set, worst case all nodes |
| Traversal | Deepest first | Follows one branch to the end before others |
| Data structure | Stack (or recursion) | LIFO order drives the depth-first behavior |
Step by step
| Step | What happens |
|---|---|
| 1 | Push the source node onto the stack. |
| 2 | Pop a node; if already visited, skip it. |
| 3 | Mark it visited and record the edge that reached it. |
| 4 | Push all its unvisited neighbors onto the stack. |
| 5 | Repeat until the stack is empty. |
Worked example
Iterative DFS from A on the graph A → [B, C], B → [D], C → [E], pushing neighbors in listed order (LIFO stack pops the last-pushed first):
| Step | Stack (top on right) | Visited | Action |
|---|---|---|---|
| 1 | [A] | {} | Push source A. |
| 2 | [B, C] | {A} | Pop A, mark visited, push neighbors B then C. |
| 3 | [B, E] | {A, C} | Pop C, mark visited, push neighbor E. |
| 4 | [B] | {A, C, E} | Pop E, mark visited, no neighbors. |
| 5 | [D] | {A, C, E, B} | Pop B, mark visited, push neighbor D. |
| 6 | [] | {A, C, E, B, D} | Pop D, mark visited, stack empty - done. |
When to use DFS
| Use it when | Avoid it when |
|---|---|
| You need cycle detection, topological sort, or to find connected components. | You need the shortest path in an unweighted graph - BFS does that, DFS does not. |
| The graph is wide and shallow, so a stack uses far less memory than a queue of many frontier nodes. | The graph is very deep and you use recursion - the call stack can overflow. |
| You want to exhaustively explore paths, as in maze solving or backtracking search. | You need nodes discovered in order of distance from the source. |
| You are checking reachability or whether a path between two nodes exists. | You must guarantee the minimum number of edges on the found path. |
Depth-First Search code
A clean, runnable Depth-First Search implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Depth-First Search code in Python
Python
1def dfs(graph, node, visited):2 visited.add(node)3 order = [node]4 for neighbor in graph[node]:5 if neighbor not in visited:6 order.extend(dfs(graph, neighbor, visited))7 return order8
9
10graph = {11 "A": ["B", "C"],12 "B": ["D", "E"],13 "C": ["F"],14 "D": [],15 "E": ["F"],16 "F": [],17}18
19order = dfs(graph, "A", set())20print("DFS order:", " -> ".join(order))Depth-First Search code in JavaScript
JavaScript
1const graph = {2 A: ["B", "C"],3 B: ["D", "E"],4 C: ["F"],5 D: [],6 E: ["F"],7 F: [],8};9
10function dfs(node, visited = new Set(), order = []) {11 if (visited.has(node)) return order;12 visited.add(node);13 order.push(node);14 for (const next of graph[node]) {15 dfs(next, visited, order);16 }17 return order;18}19
20console.log("DFS from A:", dfs("A").join(" -> "));Depth-First Search code in Java
Java
1import java.util.List;2
3public class Main {4 static List<List<Integer>> adj = List.of(5 List.of(1, 2), // neighbors of 06 List.of(0, 3, 4), // neighbors of 17 List.of(0, 5), // neighbors of 28 List.of(1),9 List.of(1, 5),10 List.of(2, 4)11 );12 static boolean[] visited = new boolean[6];13
14 static void dfs(int node) {15 visited[node] = true;16 System.out.print(" " + node);17 for (int next : adj.get(node)) {18 if (!visited[next]) dfs(next);19 }20 }21
22 public static void main(String[] args) {23 System.out.print("DFS from 0:");24 dfs(0);25 System.out.println();26 }27}Depth-First Search code in C++
C++
1#include <iostream>2#include <vector>3
4void dfs(int node, const std::vector<std::vector<int>>& adj,5 std::vector<bool>& visited) {6 visited[node] = true;7 std::cout << node << " ";8 // Recurse into every unvisited neighbor9 for (int next : adj[node]) {10 if (!visited[next]) dfs(next, adj, visited);11 }12}13
14int main() {15 // 6-node undirected graph as an adjacency list16 std::vector<std::vector<int>> adj = {17 {1, 2}, // 018 {0, 3, 4}, // 119 {0, 5}, // 220 {1}, // 321 {1, 5}, // 422 {2, 4}, // 523 };24 std::vector<bool> visited(adj.size(), false);25 std::cout << "DFS from node 0: ";26 dfs(0, adj, visited);27 std::cout << "\n";28 return 0;29}Depth-First Search code in C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6// 6-node undirected graph as an adjacency matrix7int adj[N][N] = {8 {0, 1, 1, 0, 0, 0},9 {1, 0, 0, 1, 1, 0},10 {1, 0, 0, 0, 0, 1},11 {0, 1, 0, 0, 0, 0},12 {0, 1, 0, 0, 0, 1},13 {0, 0, 1, 0, 1, 0},14};15bool visited[N];16
17void dfs(int node) {18 visited[node] = true;19 printf("%d ", node);20 // Recurse into every unvisited neighbor21 for (int next = 0; next < N; next++) {22 if (adj[node][next] && !visited[next]) dfs(next);23 }24}25
26int main(void) {27 printf("DFS from node 0: ");28 dfs(0);29 printf("\n");30 return 0;31}Depth-First Search FAQ
What is the time complexity of DFS?
DFS runs in
O(V + E) time, where V is the number of vertices and E the number of edges, because it visits each vertex once and looks at each edge once. It uses O(V) space for the stack and visited set.What is the difference between DFS and BFS?
DFS uses a stack and dives deep along one branch before backtracking, while BFS uses a queue and explores level by level, nearest nodes first. BFS finds the shortest path in an unweighted graph; DFS does not, but uses less memory on wide graphs and is natural for tasks like cycle detection and topological sorting.
Is DFS recursive or iterative?
Both work. The recursive version uses the program's call stack implicitly and is very concise; the iterative version uses an explicit stack (like the animation here) and avoids deep-recursion stack overflows on large graphs.
When should I use DFS instead of BFS?
Use DFS when you need to explore whole paths - cycle detection, topological sorting, connected components, or backtracking search like solving a maze. It also uses less memory on wide graphs, since the stack only holds one branch's frontier at a time. Reach for BFS instead whenever you need the shortest path in an unweighted graph or nodes in order of distance from the source.
Can DFS find the shortest path?
Not reliably. DFS returns the first path it happens to find, which is often not the one with the fewest edges, because it commits to diving deep rather than expanding outward evenly. For shortest paths in an unweighted graph use BFS, and for weighted graphs use Dijkstra's algorithm.
Why does DFS need a visited set?
Without a visited set, DFS will revisit nodes reachable by multiple paths and, in a cyclic graph, loop forever. Marking a node visited when you pop it (and skipping already-visited pops) guarantees every node is processed once and keeps the running time at
O(V + E). A common mistake is marking nodes visited only when popping while still pushing duplicates, which is correct but can leave stale entries on the stack that must be skipped.Related resources
More visualizations
