DFS Depth First Search on Graph in DSA C - Build from Scratch

DFS Depth First Search on Graph

📖 Scenario: You are working with a simple map of connected cities. Each city is connected to some other cities by roads. You want to explore all cities reachable from a starting city using Depth First Search (DFS).

🎯 Goal: Build a program that uses DFS to visit all cities connected to a starting city and prints the order of visiting.

📋 What You'll Learn

Create an adjacency list to represent the graph of cities

Create a visited array to track visited cities

Implement DFS using recursion

Print the order of cities visited by DFS

💡 Why This Matters

🌍 Real World

DFS is used in many real-world problems like finding connected components, solving puzzles, and exploring networks.

💼 Career

Understanding DFS is essential for software engineers working on graph algorithms, network analysis, and problem-solving.

1

Create the graph adjacency list

Create an integer 2D array called graph with 4 rows and 4 columns representing the adjacency matrix of the graph. Initialize it with these exact values: row 0: {0, 1, 1, 0}, row 1: {1, 0, 0, 1}, row 2: {1, 0, 0, 1}, row 3: {0, 1, 1, 0}.

DSA C

// Create the adjacency matrix graph with 4 nodes
// Your code here

Hint

Use a 2D array with 4 rows and 4 columns. Each row is an array of 4 integers.

2

Create the visited array

Create an integer array called visited of size 4 and initialize all elements to 0.

DSA C

int graph[4][4] = {
    {0, 1, 1, 0},
    {1, 0, 0, 1},
    {1, 0, 0, 1},
    {0, 1, 1, 0}
};

// Create visited array with 4 zeros
// Your code here

Hint

Use an integer array of size 4 and initialize all elements to zero.

3

Implement the DFS function

Write a recursive function called dfs that takes an integer node as input. Inside the function, mark visited[node] as 1. Then use a for loop with variable i from 0 to 3 to check if graph[node][i] is 1 and visited[i] is 0. If yes, call dfs(i) recursively.

DSA C

int graph[4][4] = {
    {0, 1, 1, 0},
    {1, 0, 0, 1},
    {1, 0, 0, 1},
    {0, 1, 1, 0}
};

int visited[4] = {0, 0, 0, 0};

// Write the dfs function below
// Your code here

Hint

Mark the node visited, then loop over all nodes to find connected unvisited nodes and call dfs recursively.

4

Print the DFS visiting order

In the main function, call dfs(0) to start DFS from node 0. Then use a for loop with variable i from 0 to 3 to print i if visited[i] is 1. Print all visited nodes separated by spaces on one line.

DSA C

int graph[4][4] = {
    {0, 1, 1, 0},
    {1, 0, 0, 1},
    {1, 0, 0, 1},
    {0, 1, 1, 0}
};

int visited[4] = {0, 0, 0, 0};

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

int main() {
    dfs(0);

    // Print all visited nodes separated by spaces
    // Your code here
    return 0;
}

Hint

After DFS, print all nodes where visited[i] is 1 separated by spaces.