DFS Depth First Search

DFS is like exploring a cave by following one tunnel as far as it goes, then backing up to try the next tunnel.

In this page:

What is DFS
Recursive DFS
Visited Array
DFS Uses
Complexity

Syntax

markup

def dfs(node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited)

What is DFS

Depth-First Search dives down one path as far as it can go before backtracking to try the next unexplored option, much like solving a maze by always taking the first turn and only retreating when you hit a dead end. It contrasts with BFS, which spreads out level by level instead of committing to a single path first.

Example: What is DFS

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj = {{1,2},{0,3},{0,3},{1,2}};
bool visited[4] = {false};
void dfs(int u) {
	visited[u] = true; cout << u << " ";
	for (int v : adj[u]) if (!visited[v]) dfs(v);
}
int main() {
	cout << "DFS order from 0: ";
	dfs(0);
	return 0;
}

import java.util.*;
public class Main {
	static List<List<Integer>> adj = Arrays.asList(Arrays.asList(1,2), Arrays.asList(0,3), Arrays.asList(0,3), Arrays.asList(1,2));
	static boolean[] visited = new boolean[4];
	static void dfs(int u) {
		visited[u] = true; System.out.print(u + " ");
		for (int v : adj.get(u)) if (!visited[v]) dfs(v);
	}
	public static void main(String[] args) {
		System.out.print("DFS order from 0: ");
		dfs(0);
	}
}

adj = [[1,2],[0,3],[0,3],[1,2]]
visited = [False]*4
def dfs(u):
    visited[u] = True
    print(u, end=" ")
    for v in adj[u]:
        if not visited[v]:
            dfs(v)
print("DFS order from 0:", end=" ")
dfs(0)

#include <stdio.h>
int adj[4][2] = {{1,2},{0,3},{0,3},{1,2}};
int visited[4] = {0};
void dfs(int u) {
	visited[u] = 1;
	printf("%d ", u);
	for (int i = 0; i < 2; i++) if (!visited[adj[u][i]]) dfs(adj[u][i]);
}
int main() {
	printf("DFS order from 0: ");
	dfs(0);
	return 0;
}

Recursive DFS

Because DFS naturally follows a 'go deep, then backtrack' pattern, the call stack itself can track which vertex to return to next, so a recursive function that calls itself on each unvisited neighbor implements DFS with almost no extra bookkeeping.

Example: Recursive DFS

#include <iostream>
using namespace std;
void goDeep(int depth) {
	if (depth == 0) { cout << "Hit dead end, backtracking"; return; }
	cout << "Descend to depth " << depth << " -> ";
	goDeep(depth - 1);
}
int main() {
	goDeep(3);
	return 0;
}

public class Main {
	static void goDeep(int depth) {
		if (depth == 0) { System.out.print("Hit dead end, backtracking"); return; }
		System.out.print("Descend to depth " + depth + " -> ");
		goDeep(depth - 1);
	}
	public static void main(String[] args) {
		goDeep(3);
	}
}

def go_deep(depth):
    if depth == 0:
        print("Hit dead end, backtracking", end="")
        return
    print(f"Descend to depth {depth} -> ", end="")
    go_deep(depth - 1)
go_deep(3)

#include <stdio.h>
void goDeep(int depth) {
	if (depth == 0) { printf("Hit dead end, backtracking"); return; }
	printf("Descend to depth %d -> ", depth);
	goDeep(depth - 1);
}
int main() {
	goDeep(3);
	return 0;
}

Visited Array

Without tracking visited vertices, DFS would loop forever on any graph containing a cycle, revisiting the same nodes endlessly. A boolean array (or set) marked the moment a vertex is first entered stops the recursion from re-exploring it.

Example: Visited Array

#include <iostream>
using namespace std;
int adj[3][1] = {{1},{2},{0}};
bool visited[3] = {false};
void dfs(int u, int depth) {
	if (depth > 5) { cout << "would loop forever without visited check"; return; }
	if (visited[u]) { cout << "already visited " << u << ", stop recursing"; return; }
	visited[u] = true;
	dfs(adj[u][0], depth+1);
}
int main() { dfs(0, 0); return 0; }

public class Main {
	static int[][] adj = {{1},{2},{0}};
	static boolean[] visited = new boolean[3];
	static void dfs(int u) {
		if (visited[u]) { System.out.print("already visited " + u + ", stop recursing"); return; }
		visited[u] = true;
		dfs(adj[u][0]);
	}
	public static void main(String[] args) { dfs(0); }
}

adj = [[1],[2],[0]]
visited = [False]*3
def dfs(u):
    if visited[u]:
        print(f"already visited {u}, stop recursing", end="")
        return
    visited[u] = True
    dfs(adj[u][0])
dfs(0)

#include <stdio.h>
int adj[3][1] = {{1},{2},{0}};
int visited[3] = {0};
void dfs(int u) {
	if (visited[u]) { printf("already visited %d, stop recursing", u); return; }
	visited[u] = 1;
	dfs(adj[u][0]);
}
int main() { dfs(0); return 0; }

DFS Uses

DFS is the standard tool for finding connected components, checking whether a path exists between two vertices, detecting cycles, and computing topological orderings — anywhere you need to fully explore reachability from a starting point.

Example: DFS Uses

#include <iostream>
using namespace std;
int main() {
	cout << "DFS: connected components, path existence, cycle detection, topological order";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("DFS: connected components, path existence, cycle detection, topological order");
	}
}

print("DFS: connected components, path existence, cycle detection, topological order")

#include <stdio.h>
int main() {
	printf("DFS: connected components, path existence, cycle detection, topological order");
	return 0;
}

Complexity

Each vertex is visited once and each edge is examined once when using an adjacency list, giving O(V+E) time; an adjacency matrix instead costs O(V²) because every row must be scanned even for sparse graphs.

Example: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "DFS with adjacency list: O(V+E); with adjacency matrix: O(V^2)";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("DFS with adjacency list: O(V+E); with adjacency matrix: O(V^2)");
	}
}

print("DFS with adjacency list: O(V+E); with adjacency matrix: O(V^2)")

#include <stdio.h>
int main() {
	printf("DFS with adjacency list: O(V+E); with adjacency matrix: O(V^2)");
	return 0;
}

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson BFS Breadth First Search Next Lesson → Cycle Detection