Cycle Detection in Directed Graph in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection using DFS

What is the output of the following C code that detects a cycle in a directed graph using DFS?

DSA C

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

#define V 4

bool dfs(int v, bool graph[V][V], bool visited[V], bool recStack[V]) {
    if(!visited[v]) {
        visited[v] = true;
        recStack[v] = true;

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

bool isCyclic(bool graph[V][V]) {
    bool visited[V] = {false};
    bool recStack[V] = {false};

    for(int i = 0; i < V; i++) {
        if(dfs(i, graph, visited, recStack))
            return true;
    }
    return false;
}

int main() {
    bool graph[V][V] = {
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1},
        {1, 0, 0, 0}
    };

    if(isCyclic(graph))
        printf("Cycle detected\n");
    else
        printf("No cycle detected\n");

    return 0;
}

A Cycle detected

B No cycle detected

C Compilation error

D Runtime error

💡 Hint

Trace the DFS calls and check if any node is revisited in the current recursion stack.

The graph has edges 0->1, 1->2, 2->3, and 3->0 forming a cycle. The DFS detects this cycle by checking the recursion stack.

🧠 Conceptual

intermediate

Understanding recursion stack in cycle detection

In cycle detection for a directed graph using DFS, what is the purpose of the recursion stack (recStack) array?

A To keep track of all visited nodes globally

B To keep track of nodes currently in the recursion path to detect back edges

C To store the order of nodes visited for topological sort

D To count the number of edges from each node

💡 Hint

Think about how a cycle is detected during DFS traversal.

The recursion stack marks nodes currently being explored. If a node is revisited while still in the recursion stack, it means a cycle exists.

🔧 Debug

advanced

Identify the error in cycle detection code

What error will occur when running this modified cycle detection code?

DSA C

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

#define V 3

bool dfs(int v, bool graph[V][V], bool visited[V], bool recStack[V]) {
    visited[v] = true;
    recStack[v] = true;

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

bool isCyclic(bool graph[V][V]) {
    bool visited[V] = {false};
    bool recStack[V] = {false};

    for(int i = 0; i < V; i++) {
        if(dfs(i, graph, visited, recStack))
            return true;
    }
    return false;
}

int main() {
    bool graph[V][V] = {
        {0, 1, 0},
        {0, 0, 1},
        {0, 0, 0}
    };

    if(isCyclic(graph))
        printf("Cycle detected\n");
    else
        printf("No cycle detected\n");

    return 0;
}

A No error, prints 'Cycle detected'

B Stack overflow due to infinite recursion

C Array index out of bounds error

D Compilation error due to missing header

💡 Hint

Check the loop bounds in isCyclic function.

The loop in isCyclic runs from 0 to V inclusive, causing an out-of-bounds access when i == V.

🚀 Application

advanced

Detect cycle in a graph with multiple disconnected components

Given a directed graph with 5 nodes and edges: 0->1, 1->2, 3->4, 4->3, which statement about cycle detection is true?

A The graph has a cycle only in the component containing nodes 3 and 4

B The graph has no cycles because components are disconnected

C The graph has a cycle in the component containing nodes 0,1,2

D The graph has cycles in both components

💡 Hint

Check edges in each disconnected component separately.

Nodes 3 and 4 form a cycle (3->4 and 4->3). The other component 0->1->2 has no cycle.

🧠 Conceptual

expert

Why can't BFS alone detect cycles in directed graphs reliably?

Why is BFS not typically used alone to detect cycles in directed graphs?

A BFS can only detect cycles in undirected graphs

B BFS always detects cycles incorrectly in directed graphs

C BFS requires more memory than DFS for cycle detection

D BFS cannot detect back edges which indicate cycles in directed graphs

💡 Hint

Think about how cycle detection relies on back edges and recursion stack.

Cycle detection in directed graphs depends on detecting back edges during DFS. BFS does not track recursion paths and thus cannot reliably detect cycles alone.