Depth First Search (DFS) Algorithm | Recursive Graph Traversal

Description

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Starting from a chosen source vertex, it explores the graph by going deeper through adjacent nodes before visiting sibling nodes. DFS is particularly useful for:

Detecting cycles in a graph
Finding connected components
Topological sorting
Solving puzzles with only one solution (like mazes)
Finding strongly connected components

Visualization

Speed:

Click on a node to start DFS traversal

How It Works

DFS works by following these steps:

Start at a chosen vertex (root node)
Mark the current vertex as visited
Recursively visit any unvisited adjacent vertices
Backtrack when no unvisited adjacent vertices remain

Key Characteristics

Uses a stack (or recursion) for implementation
Memory efficient for deep graphs
Can get stuck in infinite paths without cycle detection
Not guaranteed to find shortest paths

Implementation


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

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')  # Process current vertex
            
            # Add unvisited neighbors to stack
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)

#include <stack>
#include <vector>
#include <unordered_set>

void dfs_recursive(const vector<vector<int>>& graph, int vertex,
                  unordered_set<int>& visited) {
    visited.insert(vertex);
    cout << vertex << " ";  // Process current vertex
    
    for (int neighbor : graph[vertex]) {
        if (visited.find(neighbor) == visited.end()) {
            dfs_recursive(graph, neighbor, visited);
        }
    }
}

void dfs_iterative(const vector<vector<int>>& graph, int start) {
    unordered_set<int> visited;
    stack<int> s;
    s.push(start);
    
    while (!s.empty()) {
        int vertex = s.top();
        s.pop();
        
        if (visited.find(vertex) == visited.end()) {
            visited.insert(vertex);
            cout << vertex << " ";  // Process current vertex
            
            // Add unvisited neighbors to stack
            for (int i = graph[vertex].size() - 1; i >= 0; --i) {
                int neighbor = graph[vertex][i];
                if (visited.find(neighbor) == visited.end()) {
                    s.push(neighbor);
                }
            }
        }
    }
}

public class DFS {
    public void DfsRecursive(Dictionary<int, List<int>> graph, 
                            int vertex, HashSet<int> visited = null)
    {
        visited ??= new HashSet<int>();
        
        visited.Add(vertex);
        Console.Write($"{vertex} ");  // Process current vertex
        
        foreach (int neighbor in graph[vertex])
        {
            if (!visited.Contains(neighbor))
            {
                DfsRecursive(graph, neighbor, visited);
            }
        }
    }
    
    public void DfsIterative(Dictionary<int, List<int>> graph, int start)
    {
        var visited = new HashSet<int>();
        var stack = new Stack<int>();
        stack.Push(start);
        
        while (stack.Count > 0)
        {
            int vertex = stack.Pop();
            if (!visited.Contains(vertex))
            {
                visited.Add(vertex);
                Console.Write($"{vertex} ");  // Process current vertex
                
                // Add unvisited neighbors to stack
                foreach (int neighbor in graph[vertex].Reverse())
                {
                    if (!visited.Contains(neighbor))
                    {
                        stack.Push(neighbor);
                    }
                }
            }
        }
    }
}

Complexity Analysis

Operation	Time Complexity	Space Complexity
Worst Case	O(V + E)	O(V)
Average Case	O(V + E)	O(V)
Best Case	O(1)	O(1)

Where V is the number of vertices and E is the number of edges in the graph.

Advantages and Disadvantages

Advantages

Memory efficient for deep graphs
Naturally recursive implementation
Useful for finding paths and cycles
Good for topological sorting
Simple to implement

Disadvantages

Can get stuck in infinite paths
Not guaranteed to find shortest path
May use more stack space in recursive implementation
Less suitable for finding shortest paths
Can be slower for shallow, wide graphs

Applications

Solving mazes and puzzles
Topological sorting in DAGs
Finding connected components
Cycle detection in graphs
Path finding in game trees
Web crawling

Quick Info

Depth First Search (DFS)