Depth-First Search (DFS) is a graph traversal algorithm that explores a path as far as possible before backtracking. Instead of moving level by level, DFS keeps going deeper into the graph until it cannot continue, then returns to the most recent vertex that still has an unexplored neighbor.
DFS is not just a traversal method. It is a general graph exploration framework that becomes the foundation for many advanced algorithms. Once we know how to visit vertices deeply and backtrack correctly, we can build cycle detection, topological sorting, strongly connected components, articulation points, bridges, and several backtracking techniques on top of it.
Imagine exploring a maze. At every junction, you choose one path and keep walking until you hit a dead end. Then you backtrack to the previous junction and try another path. That is exactly how DFS behaves on a graph.
| Concept | Meaning in DFS |
|---|---|
| Visited array / set | Ensures each vertex is processed once |
| Call stack | Stores the path in recursive DFS |
| Explicit stack | Used in iterative DFS |
| Backtracking | Return to a previous vertex after exploring a branch |
| Discovery time / finish time | Useful in advanced DFS applications |
Suppose the graph has edges: 0-1, 0-2, 1-3, 1-4, 2-5. If DFS starts at 0 and processes neighbors from left to right, one valid traversal is:
0 -> 1 -> 3, backtrack to 1, then 4, backtrack to 0, then 2 -> 5.
So one possible DFS order is: 0, 1, 3, 4, 2, 5. DFS order is not unique; it depends on the order of neighbors.
As DFS runs, it builds a DFS tree (or DFS forest if the graph is disconnected). Every recursive call that discovers a new vertex becomes a tree edge. This tree records how vertices were first reached during traversal.
| Approach | How it Works | When to Use |
|---|---|---|
| Recursive DFS | Uses the system call stack automatically | Cleaner code, easier to understand |
| Iterative DFS | Uses an explicit stack data structure | Better control, avoids stack overflow on deep graphs |
import java.util.*;
public class DFS {
static int V;
static List<List<Integer>> adj;
static void buildGraph(int v) {
V = v;
adj = new ArrayList<>();
for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
}
static void addEdge(int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u); // undirected graph
}
// Recursive DFS - O(V + E)
static void dfsRecursive(int node, boolean[] visited) {
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfsRecursive(neighbor, visited);
}
}
}
// Iterative DFS using stack
static void dfsIterative(int src) {
boolean[] visited = new boolean[V];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(src);
System.out.print("Iterative DFS: ");
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited[node]) continue;
visited[node] = true;
System.out.print(node + " ");
for (int i = adj.get(node).size() - 1; i >= 0; i--) {
int neighbor = adj.get(node).get(i);
if (!visited[neighbor]) {
stack.push(neighbor);
}
}
}
System.out.println();
}
// Cycle detection in an undirected graph
static boolean hasCycle(int node, int parent, boolean[] visited) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
if (hasCycle(neighbor, node, visited)) return true;
} else if (neighbor != parent) {
return true;
}
}
return false;
}
public static void main(String[] args) {
buildGraph(6);
addEdge(0, 1); addEdge(0, 2);
addEdge(1, 3); addEdge(1, 4);
addEdge(2, 5);
boolean[] visited = new boolean[V];
System.out.print("Recursive DFS: ");
dfsRecursive(0, visited);
System.out.println();
dfsIterative(0);
buildGraph(4);
addEdge(0, 1); addEdge(1, 2);
addEdge(2, 3); addEdge(3, 1);
boolean[] vis2 = new boolean[V];
System.out.println("Graph has cycle: " + hasCycle(0, -1, vis2));
}
}If the graph is disconnected, starting DFS from a single source will only visit one connected component. To traverse the entire graph, we run DFS from every still-unvisited vertex.
This idea is also why we speak of a DFS forest instead of a single DFS tree in disconnected graphs.
| Graph Type | How DFS Detects a Cycle |
|---|---|
| Undirected graph | If we reach a visited neighbor that is not the parent, a cycle exists |
| Directed graph | If we reach a vertex currently in the recursion stack, a back edge exists and a cycle is present |
This distinction is important. The parent trick works for undirected graphs, but directed graphs require tracking whether a node is currently active in the recursive call chain.
For a Directed Acyclic Graph (DAG), DFS can produce a topological ordering. The key idea is to push a vertex onto a stack after all of its outgoing neighbors have been processed. This ensures every dependency appears before the task that depends on it.
import java.util.*;
public class TopologicalSort {
static int V;
static List<List<Integer>> adj;
static void buildGraph(int v) {
V = v;
adj = new ArrayList<>();
for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
}
static void addEdge(int u, int v) {
adj.get(u).add(v); // directed edge u -> v
}
static void dfs(int node, boolean[] visited, Deque<Integer> order) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) dfs(neighbor, visited, order);
}
order.push(node);
}
static void topologicalSort() {
boolean[] visited = new boolean[V];
Deque<Integer> order = new ArrayDeque<>();
for (int i = 0; i < V; i++) {
if (!visited[i]) dfs(i, visited, order);
}
System.out.print("Topological order: ");
while (!order.isEmpty()) System.out.print(order.pop() + " ");
System.out.println();
}
public static void main(String[] args) {
buildGraph(6);
addEdge(5, 2); addEdge(5, 0);
addEdge(4, 0); addEdge(4, 1);
addEdge(2, 3); addEdge(3, 1);
topologicalSort(); // one valid answer: 5 4 2 3 1 0
}
}In advanced DFS-based algorithms, we often record two timestamps for each vertex:
These timestamps help in topological sorting, strongly connected components, edge classification, and articulation-point/bridge algorithms.
In directed graphs, DFS edges are often classified into types:
This classification is useful mostly in theoretical analysis and in advanced graph algorithms.
DFS naturally gives two useful orders:
Topological sorting with DFS relies on the postorder idea: push a vertex after exploring all of its outgoing neighbors.
| Measure | Value | Reason |
|---|---|---|
| Time complexity | O(V + E) | Every vertex and edge is processed at most once |
| Space complexity | O(V) | Visited array plus recursion stack or explicit stack |
| Risk in recursion | Stack overflow | Can happen on very deep graphs |
DFS and BFS are both graph traversal algorithms, but they serve different purposes. DFS is usually preferred when we care about structure, recursion, backtracking, and dependency order. BFS is preferred when we care about levels and shortest paths in unweighted graphs.
| Feature | BFS | DFS |
|---|---|---|
| Main structure | Queue | Stack / recursion |
| Traversal style | Layered | Deep exploration |
| Shortest path in unweighted graph | Yes | No |
| Common strength | Distance and minimum hops | Structure analysis and backtracking |
Explore 500+ free tutorials across 20+ languages and frameworks.