Your Progress

10/30 completed

33% complete. Continue learning to master DSA!

Depth-First Search (DFS) Algorithm

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's like exploring a maze by following a path until you hit a dead end, then backtracking to explore other paths.

💡 Key Takeaways

DFS explores vertices by going as deep as possible before backtracking
It uses a stack (explicitly or through recursion) to keep track of vertices
Time complexity is O(V + E), where V is the number of vertices and E is the number of edges
DFS is used for topological sorting, finding connected components, and solving puzzles
DFS can be implemented recursively or iteratively

How Depth-First Search Works

Depth-First Search traverses a graph by exploring as far as possible along each branch before backtracking. The algorithm works as follows:

Start at a selected node (usually called the root or source node)
Mark the current node as visited
Explore each adjacent unvisited node recursively
When there are no more unvisited adjacent nodes, backtrack to the previous node
Continue this process until all nodes reachable from the source are visited

Recursion and Backtracking

DFS naturally implements recursion and backtracking. The algorithm recursively explores each path to its fullest before backing up. This property makes DFS particularly useful for problems that require exhaustive path exploration, like finding all solutions to a maze.

Visual Representation

DFS Order:

A → B → D → E → C → F → G

Visual representation of DFS traversal on a simple graph

Note: DFS traversal is not unique and depends on the order in which adjacent vertices are considered. The visualization above shows one possible DFS traversal order, but different implementations might produce different valid DFS orders.

DFS Implementation

Depth-First Search can be implemented in two ways: recursively or iteratively using a stack. Below are implementations of both approaches in multiple programming languages:

Recursive DFS Implementation

The recursive implementation is more intuitive and leverages the system's call stack:

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5// Graph structure using adjacency list representation
6typedef struct Node {
7    int vertex;
8    struct Node* next;
9} Node;
10
11typedef struct Graph {
12    int numVertices;
13    Node** adjLists;
14    bool* visited;
15} Graph;
16
17// Create a new node
18Node* createNode(int v) {
19    Node* newNode = (Node*)malloc(sizeof(Node));
20    newNode->vertex = v;
21    newNode->next = NULL;
22    return newNode;
23}
24
25// Create a graph with n vertices
26Graph* createGraph(int n) {
27    Graph* graph = (Graph*)malloc(sizeof(Graph));
28    graph->numVertices = n;
29    
30    // Create an array of adjacency lists
31    graph->adjLists = (Node**)malloc(n * sizeof(Node*));
32    graph->visited = (bool*)malloc(n * sizeof(bool));
33    
34    // Initialize adjacency lists and visited array
35    for (int i = 0; i < n; i++) {
36        graph->adjLists[i] = NULL;
37        graph->visited[i] = false;
38    }
39    
40    return graph;
41}
42
43// Add an edge to an undirected graph
44void addEdge(Graph* graph, int src, int dest) {
45    // Add edge from src to dest
46    Node* newNode = createNode(dest);
47    newNode->next = graph->adjLists[src];
48    graph->adjLists[src] = newNode;
49    
50    // Add edge from dest to src (for undirected graph)
51    newNode = createNode(src);
52    newNode->next = graph->adjLists[dest];
53    graph->adjLists[dest] = newNode;
54}
55
56// DFS recursive implementation
57void DFSRecursive(Graph* graph, int vertex) {
58    // Mark the current vertex as visited
59    graph->visited[vertex] = true;
60    printf("%d ", vertex);
61    
62    // Recur for all adjacent vertices
63    Node* adjList = graph->adjLists[vertex];
64    while (adjList) {
65        int connectedVertex = adjList->vertex;
66        
67        if (!graph->visited[connectedVertex]) {
68            DFSRecursive(graph, connectedVertex);
69        }
70        
71        adjList = adjList->next;
72    }
73}
74
75// Reset visited array for future traversals
76void resetVisited(Graph* graph) {
77    for (int i = 0; i < graph->numVertices; i++) {
78        graph->visited[i] = false;
79    }
80}
81
82// Free memory allocated for the graph
83void freeGraph(Graph* graph) {
84    if (graph) {
85        if (graph->adjLists) {
86            // Free all nodes in adjacency lists
87            for (int v = 0; v < graph->numVertices; v++) {
88                Node* current = graph->adjLists[v];
89                while (current) {
90                    Node* temp = current;
91                    current = current->next;
92                    free(temp);
93                }
94            }
95            free(graph->adjLists);
96        }
97        
98        if (graph->visited) {
99            free(graph->visited);
100        }
101        
102        free(graph);
103    }
104}
105
106int main() {
107    // Create a graph with 7 vertices (0 to 6)
108    Graph* graph = createGraph(7);
109    
110    // Add edges to create the sample graph
111    addEdge(graph, 0, 1); // A - B
112    addEdge(graph, 0, 2); // A - C
113    addEdge(graph, 1, 3); // B - D
114    addEdge(graph, 1, 4); // B - E
115    addEdge(graph, 2, 5); // C - F
116    addEdge(graph, 2, 6); // C - G
117    
118    printf("Depth-First Traversal (starting from vertex 0): ");
119    DFSRecursive(graph, 0);
120    printf("\n");
121    
122    // Free allocated memory
123    freeGraph(graph);
124    
125    return 0;
126}

Iterative DFS Implementation

The iterative implementation uses an explicit stack data structure:

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5// Stack structure for iterative DFS
6typedef struct Stack {
7    int* items;
8    int top;
9    int capacity;
10} Stack;
11
12// Graph structure using adjacency list representation
13typedef struct Node {
14    int vertex;
15    struct Node* next;
16} Node;
17
18typedef struct Graph {
19    int numVertices;
20    Node** adjLists;
21    bool* visited;
22} Graph;
23
24// Create a new stack
25Stack* createStack(int capacity) {
26    Stack* stack = (Stack*)malloc(sizeof(Stack));
27    stack->capacity = capacity;
28    stack->top = -1;
29    stack->items = (int*)malloc(capacity * sizeof(int));
30    return stack;
31}
32
33// Check if the stack is full
34bool isStackFull(Stack* stack) {
35    return stack->top == stack->capacity - 1;
36}
37
38// Check if the stack is empty
39bool isStackEmpty(Stack* stack) {
40    return stack->top == -1;
41}
42
43// Push an item onto the stack
44void push(Stack* stack, int item) {
45    if (isStackFull(stack)) {
46        printf("Stack Overflow\n");
47        return;
48    }
49    stack->items[++stack->top] = item;
50}
51
52// Pop an item from the stack
53int pop(Stack* stack) {
54    if (isStackEmpty(stack)) {
55        printf("Stack Underflow\n");
56        return -1;
57    }
58    return stack->items[stack->top--];
59}
60
61// Create a new node
62Node* createNode(int v) {
63    Node* newNode = (Node*)malloc(sizeof(Node));
64    newNode->vertex = v;
65    newNode->next = NULL;
66    return newNode;
67}
68
69// Create a graph with n vertices
70Graph* createGraph(int n) {
71    Graph* graph = (Graph*)malloc(sizeof(Graph));
72    graph->numVertices = n;
73    
74    // Create an array of adjacency lists
75    graph->adjLists = (Node**)malloc(n * sizeof(Node*));
76    graph->visited = (bool*)malloc(n * sizeof(bool));
77    
78    // Initialize adjacency lists and visited array
79    for (int i = 0; i < n; i++) {
80        graph->adjLists[i] = NULL;
81        graph->visited[i] = false;
82    }
83    
84    return graph;
85}
86
87// Add an edge to an undirected graph
88void addEdge(Graph* graph, int src, int dest) {
89    // Add edge from src to dest
90    Node* newNode = createNode(dest);
91    newNode->next = graph->adjLists[src];
92    graph->adjLists[src] = newNode;
93    
94    // Add edge from dest to src (for undirected graph)
95    newNode = createNode(src);
96    newNode->next = graph->adjLists[dest];
97    graph->adjLists[dest] = newNode;
98}
99
100// DFS iterative implementation
101void DFSIterative(Graph* graph, int startVertex) {
102    // Create a stack for DFS
103    Stack* stack = createStack(graph->numVertices);
104    
105    // Reset visited for all vertices
106    for (int i = 0; i < graph->numVertices; i++) {
107        graph->visited[i] = false;
108    }
109    
110    // Push the starting vertex
111    push(stack, startVertex);
112    
113    while (!isStackEmpty(stack)) {
114        // Pop a vertex from stack and print it
115        int currentVertex = pop(stack);
116        
117        // Skip if already visited
118        if (graph->visited[currentVertex]) {
119            continue;
120        }
121        
122        // Mark the current node as visited and print it
123        graph->visited[currentVertex] = true;
124        printf("%d ", currentVertex);
125        
126        // Get all adjacent vertices of the current vertex
127        // Push all unvisited adjacent vertices to the stack
128        Node* temp = graph->adjLists[currentVertex];
129        while (temp) {
130            int adjVertex = temp->vertex;
131            if (!graph->visited[adjVertex]) {
132                push(stack, adjVertex);
133            }
134            temp = temp->next;
135        }
136    }
137    
138    // Free the stack
139    free(stack->items);
140    free(stack);
141}
142
143// Free memory allocated for the graph
144void freeGraph(Graph* graph) {
145    if (graph) {
146        if (graph->adjLists) {
147            // Free all nodes in adjacency lists
148            for (int v = 0; v < graph->numVertices; v++) {
149                Node* current = graph->adjLists[v];
150                while (current) {
151                    Node* temp = current;
152                    current = current->next;
153                    free(temp);
154                }
155            }
156            free(graph->adjLists);
157        }
158        
159        if (graph->visited) {
160            free(graph->visited);
161        }
162        
163        free(graph);
164    }
165}
166
167int main() {
168    // Create a graph with 7 vertices (0 to 6)
169    Graph* graph = createGraph(7);
170    
171    // Add edges to create the sample graph
172    addEdge(graph, 0, 1); // A - B
173    addEdge(graph, 0, 2); // A - C
174    addEdge(graph, 1, 3); // B - D
175    addEdge(graph, 1, 4); // B - E
176    addEdge(graph, 2, 5); // C - F
177    addEdge(graph, 2, 6); // C - G
178    
179    printf("Depth-First Traversal (Iterative, starting from vertex 0): ");
180    DFSIterative(graph, 0);
181    printf("\n");
182    
183    // Free allocated memory
184    freeGraph(graph);
185    
186    return 0;
187}

Time and Space Complexity

Aspect	Complexity	Explanation
Time Complexity	O(V + E)	V is the number of vertices and E is the number of edges. In the worst case, DFS visits each vertex and explores each edge once.
Space Complexity	O(V)	For recursive implementation, space is needed for the recursion stack. In the worst case (a linear graph), the recursion stack can grow to O(V). For iterative implementation, space is needed for the stack and visited array, which is also O(V).

Efficiency Insight

The time complexity of DFS is O(V + E), which is very efficient for graph traversal. This makes it suitable for problems where you need to explore all possible paths or search for a specific node in a graph. The space complexity can be a limitation for very large graphs, especially with the recursive implementation.

Applications of Depth-First Search

DFS is a versatile algorithm with numerous applications in computer science and beyond:

Topological Sorting

DFS is used to perform topological sorting on directed acyclic graphs (DAGs). This is useful in scheduling tasks with dependencies, course prerequisites, and any situation where ordering based on dependencies is required.

Cycle Detection

DFS can efficiently detect cycles in a graph by keeping track of vertices in the current recursion stack. This is useful in detecting deadlocks in systems, circular dependencies in build systems, and more.

Connected Components

DFS can find all connected components in an undirected graph. This is useful in network analysis, image processing (finding connected regions), and social network analysis (finding communities).

Maze Solving

DFS can be used to find a path through a maze by exploring as far as possible along each branch before backtracking. It's also used in puzzle solving, game AI, and pathfinding in various applications.

Strongly Connected Components

Kosaraju's and Tarjan's algorithms use DFS to find strongly connected components in directed graphs. These are useful in analyzing complex networks, compiler optimizations, and understanding data dependencies.

Generating Spanning Trees

DFS can generate a spanning tree (a tree that includes all vertices) of a connected graph. This is useful in network design, routing algorithms, and minimum spanning tree problems.

Example: Cycle Detection using DFS

Here's an example of how DFS can be used to detect cycles in a directed graph:

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5typedef struct Node {
6    int vertex;
7    struct Node* next;
8} Node;
9
10typedef struct Graph {
11    int numVertices;
12    Node** adjLists;
13    bool* visited;
14    bool* inRecStack; // To keep track of vertices in current recursion stack
15} Graph;
16
17Node* createNode(int v) {
18    Node* newNode = (Node*)malloc(sizeof(Node));
19    newNode->vertex = v;
20    newNode->next = NULL;
21    return newNode;
22}
23
24Graph* createGraph(int vertices) {
25    Graph* graph = (Graph*)malloc(sizeof(Graph));
26    graph->numVertices = vertices;
27    graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));
28    graph->visited = (bool*)malloc(vertices * sizeof(bool));
29    graph->inRecStack = (bool*)malloc(vertices * sizeof(bool));
30    
31    for (int i = 0; i < vertices; i++) {
32        graph->adjLists[i] = NULL;
33        graph->visited[i] = false;
34        graph->inRecStack[i] = false;
35    }
36    
37    return graph;
38}
39
40void addDirectedEdge(Graph* graph, int src, int dest) {
41    Node* newNode = createNode(dest);
42    newNode->next = graph->adjLists[src];
43    graph->adjLists[src] = newNode;
44}
45
46// Recursive function to detect cycle in a directed graph
47bool isCyclicUtil(Graph* graph, int v) {
48    // Mark current node as visited and add to recursion stack
49    graph->visited[v] = true;
50    graph->inRecStack[v] = true;
51    
52    // Recur for all adjacent vertices
53    Node* temp = graph->adjLists[v];
54    while (temp) {
55        int neighbor = temp->vertex;
56        
57        // If not visited, recursively check for cycle
58        if (!graph->visited[neighbor] && isCyclicUtil(graph, neighbor))
59            return true;
60        
61        // If already in recursion stack, we found a cycle
62        else if (graph->inRecStack[neighbor])
63            return true;
64        
65        temp = temp->next;
66    }
67    
68    // Remove vertex from recursion stack
69    graph->inRecStack[v] = false;
70    return false;
71}
72
73// Check if the graph contains a cycle
74bool isCyclic(Graph* graph) {
75    // Reset visited and recursion stack flags
76    for (int i = 0; i < graph->numVertices; i++) {
77        graph->visited[i] = false;
78        graph->inRecStack[i] = false;
79    }
80    
81    // Check for cycle in each connected component
82    for (int i = 0; i < graph->numVertices; i++) {
83        if (!graph->visited[i]) {
84            if (isCyclicUtil(graph, i))
85                return true;
86        }
87    }
88    
89    return false;
90}
91
92void freeGraph(Graph* graph) {
93    for (int v = 0; v < graph->numVertices; v++) {
94        Node* current = graph->adjLists[v];
95        while (current) {
96            Node* temp = current;
97            current = current->next;
98            free(temp);
99        }
100    }
101    free(graph->adjLists);
102    free(graph->visited);
103    free(graph->inRecStack);
104    free(graph);
105}
106
107int main() {
108    // Create a graph with 4 vertices
109    Graph* graph = createGraph(4);
110    
111    // Add edges to create a cycle: 0->1->2->3->0
112    addDirectedEdge(graph, 0, 1);
113    addDirectedEdge(graph, 1, 2);
114    addDirectedEdge(graph, 2, 3);
115    addDirectedEdge(graph, 3, 0);
116    
117    if (isCyclic(graph))
118        printf("Graph contains a cycle\n");
119    else
120        printf("Graph doesn't contain a cycle\n");
121    
122    // Create a graph without a cycle
123    Graph* acyclicGraph = createGraph(4);
124    addDirectedEdge(acyclicGraph, 0, 1);
125    addDirectedEdge(acyclicGraph, 1, 2);
126    addDirectedEdge(acyclicGraph, 2, 3);
127    
128    if (isCyclic(acyclicGraph))
129        printf("Second graph contains a cycle\n");
130    else
131        printf("Second graph doesn't contain a cycle\n");
132    
133    // Free allocated memory
134    freeGraph(graph);
135    freeGraph(acyclicGraph);
136    
137    return 0;
138}

Note: This cycle detection algorithm works specifically for directed graphs. For undirected graphs, the approach needs to be modified to avoid false positives from the bidirectional nature of edges.

DFS vs. BFS: When to Use Each

Aspect	Depth-First Search (DFS)	Breadth-First Search (BFS)
Data Structure	Stack (or recursion)	Queue
Traversal Pattern	Explores deep into a branch before backtracking	Explores all neighbors at the current level before moving to the next level
Space Complexity	O(h) where h is the height of the recursion tree	O(w) where w is the maximum width of the graph
Best For	Maze solving Topological sorting Cycle detection Path finding (any path)	Shortest path (unweighted) Level-order traversal Finding all nodes at distance k Finding connected components
Implementation	Simpler with recursion	Usually iterative with a queue

Next Steps

Now that you understand Depth-First Search, you can explore these related topics:

Breadth-First Search-Learn another fundamental graph traversal algorithm
Topological Sort-Learn how to order vertices in a directed acyclic graph
Strongly Connected Components-Discover algorithms for finding strongly connected components using DFS

Introduction to DSA

Basic Data Structures

Advanced Data Structures

Searching Algorithms

Sorting Algorithms

Advanced Algorithms