DFS Program in C – Depth First Search with Example

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Starting from a source node, it follows one path all the way to a dead end, then backtracks and tries the next unvisited neighbor. DFS uses a stack — either an explicit one or the program’s call stack via recursion.

DFS is the foundation for topological sorting, cycle detection, maze solving, and finding strongly connected components in a graph.

How DFS Works — Step by Step

The algorithm maintains a visited[] array to avoid revisiting nodes.

1. Start at the source node. Mark it visited.
2. Pick any unvisited neighbor. Recurse into it (go deep).
3. When no unvisited neighbors remain, backtrack to the previous node.
4. Repeat until all reachable nodes are visited.

Example: Graph with 4 nodes — 1 connects to 2 and 3, node 2 connects to 4.

Adjacency Matrix:
    1  2  3  4
1 [ 0  1  1  0 ]
2 [ 1  0  0  1 ]
3 [ 1  0  0  0 ]
4 [ 0  1  0  0 ]

DFS from node 1:
  Visit 1 → go to first neighbor: 2
  Visit 2 → go to first unvisited neighbor: 4
  Visit 4 → no unvisited neighbors → backtrack to 2
  Backtrack to 1 → next unvisited neighbor: 3
  Visit 3 → no unvisited neighbors → backtrack

Traversal order: 1 → 2 → 4 → 3
Edges traversed: 1→2, 2→4, 1→3

Notice DFS goes deep (1→2→4) before trying 3, while BFS would have visited 2 and 3 before going to 4.

C Program for DFS (Depth First Search)

#include <stdio.h>

int a[20][20], reach[20], n;

void dfs(int v) {
    int i;
    reach[v] = 1;
    for (i = 1; i <= n; i++) {
        if (a[v][i] && !reach[i]) {
            printf("%d -> %d\n", v, i);
            dfs(i);
        }
    }
}

int main() {
    int i, j, count = 0;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        reach[i] = 0;
        for (j = 1; j <= n; j++)
            a[i][j] = 0;
    }

    printf("Enter the adjacency matrix (%d x %d):\n", n, n);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);

    printf("\nDFS traversal edges:\n");
    dfs(1);

    for (i = 1; i <= n; i++)
        if (reach[i])
            count++;

    printf("\nVisited %d of %d nodes.\n", count, n);
    if (count == n)
        printf("Graph is connected.\n");
    else
        printf("Graph is NOT connected — %d nodes unreachable from vertex 1.\n", n - count);

    return 0;
}

Code Explanation

• Global arrays a[][] and reach[]: The adjacency matrix stores the graph; reach[i] = 1 once node i is visited.
• Recursive dfs(v): Marks v visited, then iterates through all possible neighbors. For each unvisited neighbor, it prints the edge and recurses. The recursion naturally uses the call stack as DFS’s implicit stack.
• Connectivity check: After DFS completes from vertex 1, any node with reach[i] == 0 was unreachable — meaning the graph has disconnected components.
• 1-indexed arrays: The program uses 1-based indexing (loops from 1 to n) to match the natural way vertices are numbered in most textbook problems.

Sample Input and Output

Enter number of vertices: 4
Enter the adjacency matrix (4 x 4):
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0

DFS traversal edges:
1 -> 2
2 -> 4
1 -> 3

Visited 4 of 4 nodes.
Graph is connected.

Time and Space Complexity

Where V = vertices and E = edges. This program uses an adjacency matrix, so it scans all V nodes for each vertex visited — giving O(V²). Space is O(V) for the visited array plus O(V) recursion stack depth in the worst case (a linear graph).

DFS vs BFS — When to Use Which

Memory advantage of DFS: DFS only needs to remember the current path from root to the active node. BFS must store all nodes at the current level, which can be enormous in a wide graph. For deep, narrow graphs (like a maze), DFS is significantly more memory-efficient.

Applications of DFS

• Topological sorting: Ordering tasks with dependencies (build systems, course prerequisites). DFS post-order gives a valid topological order.
• Cycle detection: If DFS visits a node already on the current path, there is a cycle. Used in deadlock detection in operating systems.
• Maze solving: DFS naturally explores one path to its end before trying another — the same strategy humans use to navigate a maze.
• Strongly Connected Components: Kosaraju’s and Tarjan’s algorithms for SCCs both use DFS as their core.
• Web crawlers: Some crawlers use DFS to follow links deep into a site before backtracking.

Related Programs

• C Program to Implement BFS (Breadth First Search)
• C Program for Minimum Spanning Tree (Prim’s Algorithm)
• C Program for Binary Search Tree Traversals
• C Program for Topological Sort

As an Amazon Associate we earn from qualifying purchases.

Further Reading

The definitive reference for C — The C Programming Language by Brian Kernighan and Dennis Ritchie. Covers every concept on this site: pointers, arrays, structs, file I/O, and the standard library. Worth having on your desk.