DFS Depth First Search on Graph in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of DFS traversal on a simple graph

What is the output of the DFS traversal starting from node 0 on the given graph?

DSA C

/* Graph adjacency list representation:
0: 1, 2
1: 2
2: 0, 3
3: 3

DFS starting from node 0 */
#include <stdio.h>
#include <stdbool.h>

#define N 4

int graph[N][N] = {
    {0, 1, 1, 0},
    {0, 0, 1, 0},
    {1, 0, 0, 1},
    {0, 0, 0, 1}
};
bool visited[N] = {false};

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

int main() {
    dfs(0);
    return 0;
}

A 0 1 3 2

B 0 1 2 3

C 0 3 2 1

D 0 2 3 1

💡 Hint

Trace the DFS calls starting from node 0 and follow adjacency order.

The DFS starts at node 0, visits node 1 next (since adjacency checked in order), then node 2, then node 3.

🧠 Conceptual

intermediate

Number of nodes visited in DFS on disconnected graph

Given a graph with 5 nodes and edges only between nodes 0-1 and 2-3, how many nodes will DFS starting from node 0 visit?

A 2

B 4

C 3

D 5

💡 Hint

DFS only visits nodes reachable from the start node.

Starting at node 0, DFS visits node 0 and node 1 because they are connected. Nodes 2, 3, and 4 are disconnected and not visited.

🔧 Debug

advanced

Identify the error in DFS implementation

What error will this DFS code produce when run on a graph with 3 nodes?

DSA C

#include <stdio.h>
#include <stdbool.h>

#define N 3

int graph[N][N] = {
    {0,1,0},
    {0,0,1},
    {1,0,0}
};
bool visited[N] = {false};

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

int main() {
    dfs(0);
    return 0;
}

A No error, prints: 0 1 2

B Infinite recursion

C Segmentation fault (out of bounds array access)

D Compilation error due to missing semicolon

💡 Hint

Check the loop boundary in the DFS function.

The loop runs from i = 0 to i <= N, which means i goes up to 3, but valid indices are 0 to 2. Accessing graph[node][3] causes out of bounds access leading to segmentation fault.

📝 Syntax

advanced

Identify the syntax error in DFS code snippet

Which option contains the syntax error in the DFS function?

DSA C

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

A Missing parentheses in printf

B Missing braces around for loop body

C Incorrect function return type

D Missing semicolon after visited[node] = true

💡 Hint

Look carefully at each line for missing punctuation.

The line 'visited[node] = true' is missing a semicolon at the end, causing a syntax error.

🚀 Application

expert

DFS to detect cycle in directed graph

Which option correctly implements cycle detection using DFS in a directed graph?

DSA C

#include <stdio.h>
#include <stdbool.h>

#define N 4

int graph[N][N] = {
    {0,1,0,0},
    {0,0,1,0},
    {0,0,0,1},
    {1,0,0,0}
};
bool visited[N] = {false};
bool recStack[N] = {false};

bool dfs(int node) {
    visited[node] = true;
    recStack[node] = true;
    for (int i = 0; i < N; i++) {
        if (graph[node][i]) {
            if (!visited[i] && dfs(i))
                return true;
            else if (recStack[i])
                return true;
        }
    }
    recStack[node] = false;
    return false;
}

int main() {
    bool hasCycle = false;
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            if (dfs(i)) {
                hasCycle = true;
                break;
            }
        }
    }
    printf("%s\n", hasCycle ? "Cycle detected" : "No cycle");
    return 0;
}

A Prints: Cycle detected

B Prints: No cycle

C Compilation error due to missing return in dfs

D Runtime error due to stack overflow

💡 Hint

Check how recursion stack is used to detect back edges.

The graph contains a cycle (0->1->2->3->0). The DFS with recursion stack detects this cycle and returns true, so output is 'Cycle detected'.