C Program for DFS (Depth First Search) Traversal

A C program for DFS uses a recursive function dfs() that visits a node, marks it visited, and recursively visits all its unvisited neighbors using an adjacency matrix or list.

Examples

InputGraph with edges: 0-1, 0-2, 1-2, 2-0, 2-3, 3-3; Start node: 2

OutputVisited nodes in order: 2 0 1 3

InputGraph with edges: 0-1, 1-2; Start node: 0

OutputVisited nodes in order: 0 1 2

InputGraph with no edges; Start node: 0

OutputVisited nodes in order: 0

How to Think About It

To perform DFS, start from the chosen node, mark it visited, then explore each connected node that is not visited yet by calling the same process recursively. This way, you go deep into the graph before backtracking.

Algorithm

1

Initialize a visited array to keep track of visited nodes.

2

Start DFS from the given start node.

3

Mark the current node as visited and print it.

4

For each adjacent node, if it is not visited, recursively call DFS on it.

5

Repeat until all reachable nodes are visited.

Code

c

#include <stdio.h>
#define MAX 4

int graph[MAX][MAX] = {
    {0, 1, 1, 0},
    {0, 0, 1, 0},
    {1, 0, 0, 1},
    {0, 0, 0, 1}
};
int visited[MAX] = {0};

void dfs(int node) {
    visited[node] = 1;
    printf("%d ", node);
    for (int i = 0; i < MAX; i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            dfs(i);
        }
    }
}

int main() {
    printf("Visited nodes in order: ");
    dfs(2);
    return 0;
}

Output

Visited nodes in order: 2 0 1 3 

Dry Run

Let's trace DFS starting from node 2 on the example graph.

1

Start at node 2

Mark visited[2] = 1, print 2

2

Check neighbors of 2

Neighbors: 0 and 3 (graph[2][0]=1, graph[2][3]=1)

3

Visit neighbor 0

Mark visited[0] = 1, print 0

4

Check neighbors of 0

Neighbors: 1 and 2; 2 already visited

5

Visit neighbor 1

Mark visited[1] = 1, print 1

6

Check neighbors of 1

Neighbor: 2 already visited, no new nodes

7

Back to node 2, visit neighbor 3

Mark visited[3] = 1, print 3

8

Check neighbors of 3

Neighbor: 3 itself, already visited

Step	Current Node	Visited Array	Printed Nodes
1	2	[0,0,1,0]	2
2	0	[1,0,1,0]	2 0
3	1	[1,1,1,0]	2 0 1
4	3	[1,1,1,1]	2 0 1 3

Why This Works

Step 1: Mark node visited

The visited array prevents revisiting nodes, avoiding infinite loops.

Step 2: Recursive exploration

Calling dfs() recursively on neighbors goes deep into the graph before backtracking.

Step 3: Print order

Nodes are printed as they are first visited, showing the DFS traversal order.

Alternative Approaches

DFS using adjacency list

c

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

#define MAX 4

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

Node* graph[MAX];
int visited[MAX] = {0};

void addEdge(int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph[src];
    graph[src] = newNode;
}

void dfs(int v) {
    printf("%d ", v);
    visited[v] = 1;
    Node* temp = graph[v];
    while (temp) {
        if (!visited[temp->vertex]) dfs(temp->vertex);
        temp = temp->next;
    }
}

int main() {
    addEdge(0,1); addEdge(0,2);
    addEdge(1,2);
    addEdge(2,0); addEdge(2,3);
    addEdge(3,3);
    printf("Visited nodes in order: ");
    dfs(2);
    return 0;
}

Using adjacency lists saves memory for sparse graphs and is more flexible.

DFS using stack (iterative)

c

#include <stdio.h>
#define MAX 4

int graph[MAX][MAX] = {
    {0,1,1,0},
    {0,0,1,0},
    {1,0,0,1},
    {0,0,0,1}
};
int visited[MAX] = {0};

void dfs(int start) {
    int stack[MAX], top = -1;
    stack[++top] = start;
    while (top != -1) {
        int node = stack[top--];
        if (!visited[node]) {
            printf("%d ", node);
            visited[node] = 1;
            for (int i = MAX - 1; i >= 0; i--) {
                if (graph[node][i] && !visited[i]) {
                    stack[++top] = i;
                }
            }
        }
    }
}

int main() {
    printf("Visited nodes in order: ");
    dfs(2);
    return 0;
}

Iterative DFS uses a stack to avoid recursion, useful when recursion depth is a concern.

Complexity: O(V + E) time, O(V) space

Time Complexity

DFS visits each vertex and edge once, so time is proportional to vertices plus edges.

Space Complexity

Space is used for the visited array and recursion stack, proportional to number of vertices.

Which Approach is Fastest?

Adjacency list is faster and uses less memory for sparse graphs; adjacency matrix is simpler but uses more space.

Approach	Time	Space	Best For
Adjacency Matrix DFS (recursive)	O(V^2)	O(V^2)	Dense graphs, simple implementation
Adjacency List DFS (recursive)	O(V + E)	O(V + E)	Sparse graphs, memory efficient
DFS Iterative (stack)	O(V + E)	O(V)	Avoid recursion, large graphs