Graph Traversal Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts from a source vertex and recursively explores each neighbor as deeply as possible, one branch at a time.

Imagine you are exploring a maze. You walk down a path until you reach a dead end, then you backtrack to the last junction and try another path. This is exactly how DFS works – it goes deep before going wide.

DFS uses a stack data structure to keep track of vertices to visit next. This LIFO (Last-In-First-Out) property ensures that the most recently discovered vertex is explored first. The stack can be implemented explicitly using an array, or implicitly using recursion (which uses the system call stack).

How DFS Works?

1. Start by choosing a source vertex and marking it as visited.
2. Push the source vertex onto a stack.
3. While the stack is not empty:
   • Pop a vertex from the top of the stack – this is the current vertex.
   • Process the current vertex.
   • Explore all its unvisited neighbors:
     • Mark them as visited.
     • Push them onto the stack.
4. Repeat step 3 until the stack is empty.

Detailed Example: DFS Step-by-Step

Consider the following undirected graph:

        0
       / \
      1   2
     / \   \
    3   4   5

We want to perform DFS starting from vertex 0. We'll use an explicit stack.

Initial State

• Stack: [] (empty)
• Visited: {} (empty set)
• Result (order of traversal): []

Step-by-Step Execution

Final DFS Traversal Order: 0 → 1 → 3 → 4 → 2 → 5

Visualizing the DFS Path

DFS explores one branch completely before backtracking:

• Branch 1: 0 → 1 → 3 → (backtrack) → 4 → (backtrack) → 2 → 5
• You can see how it goes deep (0 → 1 → 3) before coming back to try other paths.

Recursive vs. Iterative DFS

DFS can be implemented in two ways:

1. Recursive DFS (Using System Call Stack)

• Advantages: Very simple and elegant code.
• Disadvantages: Can cause stack overflow for very deep graphs (recursion depth > 1000 in many languages).

2. Iterative DFS (Using Explicit Stack)

• Advantages: Better control over memory; avoids stack overflow.
• Disadvantages: Slightly more complex to write.

Both produce the same traversal order (though the exact order of neighbors may differ depending on the implementation).

Algorithms for DFS

Recursive Pseudocode

Algorithm: DFS(G, v)
Input:  G - Graph
        v - Starting vertex
Output: DFS traversal order

Step 1: START
Step 2: Mark v as visited
Step 3: Process v (print or store)
Step 4: FOR each neighbor u of v DO
Step 5:     IF u is not visited THEN
Step 6:         DFS(G, u)
Step 7: END FOR
Step 8: END

Iterative Pseudocode (Using Stack)

Algorithm: DFS_Iterative(G, start)
Input:  G - Graph
        start - Starting vertex
Output: DFS traversal order

Step 1: START
Step 2: Create a stack S
Step 3: Mark start as visited
Step 4: Push start onto S
Step 5: WHILE S is not empty DO
Step 6:     current = Pop from S
Step 7:     Process current (print or store)
Step 8:     FOR each neighbor v of current DO
Step 9:         IF v is not visited THEN
Step 10:            Mark v as visited
Step 11:            Push v onto S
Step 12:        END IF
Step 13:    END FOR
Step 14: END WHILE
Step 15: END

Implementation in C Programming

Graph Structure (Same as BFS)

We'll reuse the adjacency list implementation from the BFS post.

1. Recursive DFS Implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int vertices;
    Node** adjLists;
} Graph;

// Create a node
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Create a graph
Graph* createGraph(int v) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = v;
    graph->adjLists = (Node**)malloc(v * sizeof(Node*));
    for (int i = 0; i < v; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

// Add edge (undirected)
void addEdge(Graph* graph, int u, int v) {
    Node* newNode = createNode(v);
    newNode->next = graph->adjLists[u];
    graph->adjLists[u] = newNode;
    newNode = createNode(u);
    newNode->next = graph->adjLists[v];
    graph->adjLists[v] = newNode;
}

// Recursive DFS function
void DFS_Recursive(Graph* graph, int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%d ", vertex);
    
    Node* temp = graph->adjLists[vertex];
    while (temp != NULL) {
        int neighbor = temp->vertex;
        if (!visited[neighbor]) {
            DFS_Recursive(graph, neighbor, visited);
        }
        temp = temp->next;
    }
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 5);
    
    int* visited = (int*)calloc(graph->vertices, sizeof(int));
    printf("Recursive DFS Traversal: ");
    DFS_Recursive(graph, 0, visited);
    printf("\n");
    free(visited);
    return 0;
}

Output:

Recursive DFS Traversal: 0 1 3 4 2 5

2. Iterative DFS Implementation (Using Stack)

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

// Stack structure for iterative DFS
typedef struct Stack {
    int items[MAX];
    int top;
} Stack;

// Stack operations
void initStack(Stack* s) {
    s->top = -1;
}

int isStackEmpty(Stack* s) {
    return (s->top == -1);
}

void push(Stack* s, int value) {
    if (s->top == MAX - 1) {
        printf("Stack is full!\n");
        return;
    }
    s->items[++(s->top)] = value;
}

int pop(Stack* s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->items[(s->top)--];
}

// Iterative DFS function
void DFS_Iterative(Graph* graph, int start) {
    int* visited = (int*)calloc(graph->vertices, sizeof(int));
    Stack s;
    initStack(&s);
    
    visited[start] = 1;
    push(&s, start);
    
    printf("Iterative DFS Traversal: ");
    
    while (!isStackEmpty(&s)) {
        int current = pop(&s);
        printf("%d ", current);
        
        // Explore all neighbors of current
        Node* temp = graph->adjLists[current];
        while (temp != NULL) {
            int neighbor = temp->vertex;
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                push(&s, neighbor);
            }
            temp = temp->next;
        }
    }
    printf("\n");
    free(visited);
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 5);
    
    DFS_Iterative(graph, 0);
    return 0;
}

Output:

Iterative DFS Traversal: 0 2 5 1 4 3

Note: The recursive and iterative outputs may differ slightly in the exact order of vertices, but both are valid DFS traversals. The difference arises because the recursive version explores neighbors in the order they appear in the adjacency list, while the iterative version pushes all neighbors onto the stack before processing them.

Complexity Analysis

Time Complexity

• O(V + E) – where V is the number of vertices and E is the number of edges.
• Each vertex is pushed and popped exactly once (O(V)).
• Each edge is examined twice (in an undirected graph) or once (in a directed graph) (O(E)).

Space Complexity

• Recursive: O(V) – for the visited array and the recursion call stack (which can be O(V) in the worst case for a skewed graph).
• Iterative: O(V) – for the visited array and the explicit stack.

Advantages of DFS

1. Low Memory Usage: The stack (or recursion) only needs to store the current path, making DFS memory efficient for deep graphs (compared to BFS which stores the entire level).
2. Useful for Topological Sorting: DFS is the foundation for topological ordering in directed acyclic graphs (DAGs).
3. Detects Cycles: DFS can efficiently detect cycles in directed and undirected graphs.
4. Solves Maze Problems: DFS is ideal for finding a path (not necessarily the shortest) in a maze or puzzle.
5. Backtracking: DFS naturally lends itself to backtracking algorithms (like N-Queens, Sudoku).

Disadvantages of DFS

1. No Guaranteed Shortest Path: DFS does not find the shortest path in unweighted graphs (it finds a path, but not necessarily the minimum edge count).
2. Can Go Deep and Get Stuck: If the graph is very deep, DFS might waste time exploring a deep branch that doesn't contain the solution.
3. Recursive Overhead: The recursive version can cause stack overflow for extremely large graphs.

Real-World Applications of DFS

BFS vs. DFS: A Side-by-Side Comparison