Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as deep as possible along each branch before backtracking. It behaves like a maze solver: it follows a single path to its end, backtracks when it hits a dead end, and then tries the next available branch.

Since graphs can contain cycles, DFS uses a visited tracker (an array or set) to prevent visiting the same node more than once.

How DFS Works (Step-by-Step)

DFS naturally uses a Stack (Last-In-First-Out) structure, which is typically implemented via the function call stack in a recursive implementation.

Visualizing the Graph

Let's perform DFS on the following undirected graph starting from vertex A:

DFS Trace Sequence

Starting from A, assuming we explore adjacent vertices in alphabetical order:

1. Visit A: Mark A visited. Output: A. Stack: [A].
2. Move to B (neighbor of A): Mark B visited. Output: A B. Stack: [A, B].
3. Move to D (neighbor of B): Mark D visited. Output: A B D. Stack: [A, B, D].
4. Move to E (neighbor of D): Mark E visited. Output: A B D E. Stack: [A, B, D, E].
5. Move to F (neighbor of E): Mark F visited. Output: A B D E F. Stack: [A, B, D, E, F].
6. Backtrack from F: Neighbors of F (B, C, E) are checked. B and E are already visited. We backtrack to E, then to D, then to B.
7. Backtrack to A: From A, we visit C (unvisited neighbor). Mark C visited. Output: A B D E F C. Stack: [A, C].
8. Final Traversal Order: A -> B -> D -> E -> F -> C.

JavaScript Code Implementation

class Graph {
    constructor() {
        this.list = {};
    }
    
    addVertex(vertex) {
        if (!this.list[vertex]) this.list[vertex] = [];
    }
    
    addEdge(v1, v2) {
        this.addVertex(v1);
        this.addVertex(v2);
        this.list[v1].push(v2);
        this.list[v2].push(v1);
    }
    
    // Depth-First Search (DFS) Entry Point
    dfs(startNode) {
        const visited = {};
        const result = [];
        
        this._dfsHelper(startNode, visited, result);
        
        return result;
    }
    
    // Recursive DFS Helper
    _dfsHelper(node, visited, result) {
        // Mark current node as visited and add it to results
        visited[node] = true;
        result.push(node);
        
        const neighbors = this.list[node] || [];
        for (let neighbor of neighbors) {
            // Recursively visit all unvisited neighbors
            if (!visited[neighbor]) {
                this._dfsHelper(neighbor, visited, result);
            }
        }
    }
}
 
// Driver Code
const g = new Graph();
g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("B", "F");
g.addEdge("C", "F");
g.addEdge("D", "E");
g.addEdge("E", "F");
 
console.log("DFS Traversal:", g.dfs("A").join(" "));
// Output: DFS Traversal: A B D E F C

Complexity Analysis

• Time Complexity: $O(V + E)$
  • Each vertex is visited exactly once: $O(V)$.
  • We traverse the adjacency list of every vertex exactly once, visiting all edges: $O(E)$ (specifically $2E$ for undirected graphs).
• Space Complexity: $O(V)$
  • The recursion stack can grow up to $V$ frames in the worst case (e.g., a straight line/skewed tree graph).
  • The visited object stores up to $V$ keys.