Graph Algorithms
Graph DFS (Depth-First Search)
Goes as deep as possible along each branch before backtracking. This recursive version uses the call stack as its implicit stack.
1Detailed explanation
Depth-first search follows one branch as deep as possible before backtracking. The recursive version uses the call stack to remember where to continue.
Each vertex is marked visited on entry so cycles do not cause infinite recursion. When all neighbours of a vertex are handled, the function returns — that is the backtracking step.
DFS is the basis for cycle detection, topological sorting, connected components and many backtracking algorithms.
2Pseudocode
procedure DFS(G, u, visited)
visited ← visited ∪ {u}
visit u
for each neighbor v of u
if v ∉ visited
DFS(G, v, visited)3Interactive visualization
Call stack (bottom → top)
Traversal order
Goes as deep as possible along each branch before backtracking. This recursive version uses the call stack as its implicit stack.
4Implementations
Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.
function dfs(graph, node, visited, order) {
visited.add(node);
order.push(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited, order);
}
}
}
const edges = [["A", "B"], ["A", "C"], ["B", "D"], ["B", "E"], ["C", "F"], ["E", "F"], ["D", "G"], ["F", "G"]];
const graph = {};
for (const [u, v] of edges) {
(graph[u] ??= []).push(v);
(graph[v] ??= []).push(u);
}
const visited = new Set();
const order = [];
dfs(graph, "A", visited, order);
console.log("DFS order:", order.join(" -> "));
5Time and space complexity
Time: dfs() is called once per reachable vertex (O(V)) and each call scans that vertex's adjacency list once, so all edge checks together are O(E). Total O(V + E).
Space: The visited set holds up to V vertices and the recursion can go V levels deep on a path-shaped graph → O(V) auxiliary space.
6Common interview variations
- Iterative DFS with an explicit stack.
- Count connected components.
- Detect a cycle in an undirected / directed graph.
- Topological sort.
- Find all paths from source to target.