Alright, let's get into graphs. Up until now, we've dealt with linear structures—things that go from A to B to C. But real-world data is messy. Think of a network of servers in a data center. Server A connects to B and C; B connects back to A and also to D. It's a web. To navigate this, we need a strategy. Today, we're looking at Depth First Search (DFS).

I like to think of DFS as the "stubborn" approach. If you're in a maze, you don't look at every possible path at every intersection. You pick one direction and you keep going until you hit a wall. Only then do you backtrack to the last intersection and try the next path.

The Naive Dive

Let's start by sketching out a simple graph using an adjacency matrix. I've got four servers (0 through 3). I'll represent the connections in a 2D array where 1 means a connection exists and 0 means it doesn't.

#define V 4
int graph[V][V] = {
    {0, 1, 1, 0}, // Server 0 connects to 1 and 2
    {1, 0, 0, 1}, // Server 1 connects to 0 and 3
    {1, 0, 0, 1}, // Server 2 connects to 0 and 3
    {0, 1, 1, 0}  // Server 3 connects to 1 and 2
};

My goal is simple: start at Server 0 and visit every server reachable from it. My first instinct is recursion. If I'm at a node, I just find its neighbors and call the function again on those neighbors. Let's see what happens with this "naive" version:

void dfs(int node) {
    printf("Visiting server %d\n", node);

    for (int i = 0; i < V; i++) {
        if (graph[node][i] == 1) {
            dfs(i);
        }
    }
}

I'll call dfs(0). It should visit 0, then see 1 is a neighbor and jump to 1. From 1, it sees 0 is a neighbor... and then it jumps back to 0. Then back to 1. Then back to 0.

Exactly what you're thinking: Segmentation fault (stack overflow). We've created an infinite loop because our graph has cycles. The program just keeps diving deeper into the same two nodes until the stack runs out of memory.

Remembering Where We've Been

This is the classic DFS trap. In a tree, you only go down, so you can't loop. In a graph, you can end up right back where you started. To fix this, we need a way to mark a node as "visited."

I'll add a simple boolean array. Before I dive into a neighbor, I'll check if I've already been there. If I have, I'll ignore it. If I haven't, I'll mark it and then proceed.

void dfs(int node, int visited[]) {
    // Mark the current node as visited
    visited[node] = 1;
    printf("Visiting server %d\n", node);

    for (int i = 0; i < V; i++) {
        // Only visit if there's a connection AND we haven't been there yet
        if (graph[node][i] == 1 && !visited[i]) {
            dfs(i, visited);
        }
    }
}

Now, let's trace this mentally. We start at 0. visited[0] becomes 1. We see neighbor 1. visited[1] is 0, so we jump to dfs(1). From 1, we see neighbor 0, but visited[0] is now 1, so we skip it. Then we see neighbor 3. visited[3] is 0, so we jump to dfs(3). We keep going "deep" before we ever go "wide."

The Mechanics of the Backtrack

One thing that often trips people up is how the "backtracking" actually works. You don't have to write a specific backtrack() function. That's the magic of the call stack.

When dfs(3) finishes its loop (because all its neighbors are already visited), the function returns. But it doesn't return to the start of the program; it returns exactly to where it was called from inside dfs(1). The program then continues the for loop in dfs(1), checking the remaining neighbors. Once dfs(1) is done, it pops off the stack and returns to dfs(0).

If you run this code, you'll see the order of visitation. It's not a neat circle; it's a probe. It pushes as far as it can along one branch before reluctantly giving up and trying the next branch it saw earlier.

Here is the complete, working implementation we arrived at:

#include <stdio.h>

#define V 4

void dfs(int node, int visited[], int graph[V][V]) {
    visited[node] = 1;
    printf("Visited %d\n", node);

    for (int i = 0; i < V; i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            dfs(i, visited, graph);
        }
    }
}

int main() {
    int graph[V][V] = {
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 0, 0, 1},
        {0, 1, 1, 0}
    };
    int visited[V] = {0}; // Initialize all to 0 (not visited)

    printf("Starting DFS from Server 0:\n");
    dfs(0, visited, graph);

    return 0;
}

📋 Practical Task

Exercise: Detecting a Deadlock Loop in a Resource Graph

In operating systems, a "deadlock" often occurs when there is a cycle in a resource allocation graph (e.g., Process A holds Resource 1 and waits for Resource 2, while Process B holds Resource 2 and waits for Resource 1).

Your task is to modify the DFS logic to detect if a cycle exists in a directed graph. Instead of just printing the nodes, your function should return a boolean (or integer) value: 1 if a cycle is detected and 0 otherwise.

Requirements:

• Create a directed graph (where graph[i][j] == 1 does NOT necessarily mean graph[j][i] == 1).
• Implement a function int hasCycle(int node, int visited[], int stack[], int graph[V][V]).
• You will need a second array called stack[] (recursion stack) to keep track of nodes currently in the recursion path. If you encounter a node that is already in the stack[], you've found a cycle!
• Test your code with a graph that has a cycle (e.g., 0 → 1 → 2 → 0) and one that does not (e.g., 0 → 1 → 2).