Depth-First Search (DFS)
What is DFS?
Depth-First Search (DFS) explores a graph by going as deep as possible along each branch before backtracking. It uses a stack (or recursion) to track the path.
- Used for: cycle detection, topological sort, connected components, maze solving
- Time: O(V + E), Space: O(V) for the visited array + O(V) call stack
| Feature | BFS | DFS |
|---|---|---|
| Data structure | Queue (FIFO) | Stack / Recursion |
| Traversal order | Level by level | Deep first |
| Shortest path | Yes (unweighted) | No |
| Memory | O(V) — wide graphs use more | O(V) — deep graphs use more |
| Best for | Shortest path, level-order | Cycle detection, topological sort |
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);
}
// Recursive DFS — O(V + E)
static void dfsRec(int node, boolean[] visited) {
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) dfsRec(neighbor, visited);
}
}
// Iterative DFS using explicit stack
static void dfsIter(int src) {
boolean[] visited = new boolean[V];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(src);
System.out.print("DFS iterative from " + src + ": ");
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited[node]) {
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) stack.push(neighbor);
}
}
}
System.out.println();
}
// Cycle detection in undirected graph using DFS
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; // back edge found → cycle!
}
}
return false;
}
public static void main(String[] args) {
buildGraph(6);
addEdge(0, 1); addEdge(0, 2);
addEdge(1, 3); addEdge(2, 4); addEdge(3, 5);
boolean[] visited = new boolean[V];
System.out.print("DFS recursive from 0: ");
dfsRec(0, visited);
System.out.println(); // 0 1 3 5 2 4
dfsIter(0);
// Test cycle detection
buildGraph(4);
addEdge(0, 1); addEdge(1, 2); addEdge(2, 3); addEdge(3, 1); // cycle!
boolean[] vis2 = new boolean[V];
System.out.println("Has cycle: " + hasCycle(0, -1, vis2)); // true
}
}DFS Applications
- Cycle detection — detect back edges in directed/undirected graphs
- Topological sort — order tasks with dependencies (DAG)
- Connected components — find all connected subgraphs
- Strongly connected components — Tarjan's / Kosaraju's algorithm
- Maze solving — explore paths until exit is found
- Tree traversals — pre-order, in-order, post-order
Topological Sort using DFS
Topological sort orders vertices of a DAG such that for every directed edge u → v, vertex u comes before v. Used for task scheduling, build systems, and dependency resolution.
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
static void dfsTopoSort(int node, boolean[] visited, Deque<Integer> stack) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) dfsTopoSort(neighbor, visited, stack);
}
stack.push(node); // push AFTER all descendants are processed
}
static void topologicalSort() {
boolean[] visited = new boolean[V];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < V; i++) {
if (!visited[i]) dfsTopoSort(i, visited, stack);
}
System.out.print("Topological order: ");
while (!stack.isEmpty()) System.out.print(stack.pop() + " ");
System.out.println();
}
public static void main(String[] args) {
buildGraph(6);
// Task dependencies: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1
addEdge(5, 2); addEdge(5, 0); addEdge(4, 0);
addEdge(4, 1); addEdge(2, 3); addEdge(3, 1);
topologicalSort();
// One valid order: 5 4 2 3 1 0
// (5 and 4 have no dependencies, so they come first)
}
}