Mastering Depth First Search: A Programmer’s Guide to DFS in C

Learn Depth First Search (DFS) in C with clear examples and explanations, ideal for complex graph traversal.

Depth First Search (DFS) is a fundamental algorithm used in graph theory to traverse or search through graph data structures. The algorithm explores as far as possible along each branch before backtracking, making it an excellent choice for scenarios where you need to explore all the possibilities until a solution is found or the end is reached. It's commonly used in puzzle solving, scheduling, network analysis, and more.

Algorithm Details with Pseudo Code and Explanation

Depth First Search Algorithm:
DFS can be implemented using recursion or with a stack data structure. The recursive implementation is more straightforward, while the iterative version with a stack is often preferred to avoid potential stack overflow in languages with limited recursion depth.

Pseudo Code (Recursive Approach):

function DFS(node, visited)
    mark node as visited
    print node
    for each adjacent node to node
        if node is not visited
            DFS(adjacent node, visited)

Explanation:

The DFS function takes a node and a list or set of visited nodes:

  1. The node is first marked as visited.
  2. The node's value is processed (e.g., printed or stored).
  3. The function then iterates over each node adjacent to the current node.
  4. If an adjacent node hasn't been visited, DFS is recursively called with this node.

This method allows the algorithm to dive deep into a graph, exploring edges and vertices thoroughly before backtracking.

Implementation in C Language

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

#define MAX 100

int visited[MAX];
int adj[MAX][MAX];
int n; // Number of vertices

void DFS(int v) {
    visited[v] = 1;
    printf("%d ", v);

    for (int i = 0; i < n; i++) {
        if (adj[v][i] == 1 && !visited[i])
            DFS(i);
    }
}

void addEdge(int v1, int v2) {
    adj[v1][v2] = 1;
    adj[v2][v1] = 1; // For undirected graph
}

int main() {
    n = 5; // Example: 5 vertices
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);

    for (int i = 0; i < n; i++) {
        if (!visited[i])
            DFS(i);
    }

    return 0;
}

Explanation of the C Code:

  • Graph Representation: This example uses an adjacency matrix to represent the graph where adj[v1][v2] = 1 indicates an edge between vertices v1 and v2.
  • DFS Function: This function uses a simple recursion method to visit each vertex and its adjacent vertices deeply before backtracking.
  • addEdge Function: This utility function adds an edge between two vertices in the adjacency matrix.

Time and Space Complexity:

  • Time Complexity: 𝑂(𝑉+𝐸)O(V+E), where 𝑉V is the number of vertices and 𝐸E is the number of edges.
  • Space Complexity: 𝑂(𝑉)O(V), mainly for the storage of the visited array and the adjacency matrix.

Usage

DFS is versatile and finds applications in several fields:

  • Pathfinding and Puzzle Solving: Used in games to find paths and solve puzzles.
  • Network Analysis: Helps in analyzing network connectivity.
  • Finding Components: Efficient in discovering connected components in a graph.

Conclusion

Depth First Search is an indispensable tool in a programmer’s arsenal for graph-related problems. Its ability to explore all paths makes it suitable for applications where thoroughness is crucial, from software development to scientific research.

Subscribe to rahulv.dev | blog

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe