Depth-First Search (DFS)

DFS is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking.

How DFS Works

graph TD A((A)) --> B((B)) A --> C((C)) B --> D((D)) B --> E((E)) C --> F((F)) C --> G((G)) style A fill:#4CAF50 style B fill:#2196F3 style D fill:#FF9800 style E fill:#FF9800 style C fill:#2196F3 style F fill:#FF9800 style G fill:#FF9800

Traversal Order: A → B → D → E → C → F → G

Algorithm Steps

Start at the root node
Mark the current node as visited
Explore each unvisited neighbor recursively
Backtrack when no unvisited neighbors remain

Recursive Implementation

Python

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(node, end=' ')
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}

dfs_recursive(graph, 'A')
# Output: A B D E C F G

C#

public class Graph
{
    private Dictionary<string, List<string>> adjacencyList;
    
    public void DFS(string start)
    {
        var visited = new HashSet<string>();
        DFSRecursive(start, visited);
    }
    
    private void DFSRecursive(string node, HashSet<string> visited)
    {
        visited.Add(node);
        Console.Write(node + " ");
        
        foreach (var neighbor in adjacencyList[node])
        {
            if (!visited.Contains(neighbor))
            {
                DFSRecursive(neighbor, visited);
            }
        }
    }
}

Iterative Implementation (Using Stack)

JavaScript

function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        if (!visited.has(node)) {
            visited.add(node);
            console.log(node);
            
            // Add neighbors in reverse order for correct traversal
            for (let i = graph[node].length - 1; i >= 0; i--) {
                const neighbor = graph[node][i];
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
    
    return visited;
}

Time and Space Complexity

Metric	Complexity	Explanation
Time	O(V + E)	V = vertices, E = edges
Space (Recursive)	O(V)	Call stack depth
Space (Iterative)	O(V)	Explicit stack size

Common Applications

1. Cycle Detection

def has_cycle(graph, node, visited, rec_stack):
    visited.add(node)
    rec_stack.add(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle(graph, neighbor, visited, rec_stack):
                return True
        elif neighbor in rec_stack:
            return True  # Cycle detected
    
    rec_stack.remove(node)
    return False

2. Topological Sort

def topological_sort(graph):
    visited = set()
    stack = []
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return stack[::-1]  # Reverse for correct order

3. Path Finding

def find_path(graph, start, end, path=[]):
    path = path + [start]
    
    if start == end:
        return path
    
    for neighbor in graph[start]:
        if neighbor not in path:
            new_path = find_path(graph, neighbor, end, path)
            if new_path:
                return new_path
    
    return None

DFS vs BFS

Aspect	DFS	BFS
Data Structure	Stack (LIFO)	Queue (FIFO)
Traversal	Goes deep first	Level by level
Best For	Topological sort, cycle detection	Shortest path, level-order
Memory	Less (depth of tree)	More (width of tree)

Depth-First Search (DFS) Algorithm