Graph Cycle Detection (DFS/BFS) in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#include <stdlib.h>
int g[100][100], vis[100];
int dfs(int u, int p, int n) {
    vis[u] = 1;
    for (int v = 0; v < n; v++) {
        if (g[u][v]) {
            if (!vis[v]) {
                if (dfs(v, u, n)) return 1;
            } else if (v != p) return 1;
        }
    }
    return 0;
}
int main() {
    int n = 4;
    g[0][1] = g[1][0] = 1;
    g[1][2] = g[2][1] = 1;
    g[2][0] = g[0][2] = 1;
    printf("%s", dfs(0, -1, n) ? "Cycle Found" : "No Cycle");
}

C Output

Input:
Graph Edges: 0–1, 1–2, 2–0 (undirected)

Output:
Cycle Found

C++ Program

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool hasCycle(int n, vector<vector<int>>& g) {
    vector<bool> vis(n);
    for (int s = 0; s < n; s++) {
        if (!vis[s]) {
            queue<pair<int, int>> q;
            q.push({s, -1});
            vis[s] = true;
            while (!q.empty()) {
                int u = q.front().first, p = q.front().second; q.pop();
                for (int v : g[u]) {
                    if (!vis[v]) {
                        vis[v] = true;
                        q.push({v, u});
                    } else if (v != p) return true;
                }
            }
        }
    }
    return false;
}
int main() {
    int n = 5;
    vector<vector<int>> g(n);
    g[0] = {1}; g[1] = {0, 2}; g[2] = {1, 3}; g[3] = {2}; // No cycle
    cout << (hasCycle(n, g) ? "Cycle Found" : "No Cycle");
}

C++ Output

Input:
Graph Edges: 0–1, 1–2, 2–3 (undirected)
Output:
No Cycle

JAVA Program

import java.util.*;
public class Main {
    static boolean dfs(int u, boolean[] vis, boolean[] rec, List<List<Integer>> g) {
        vis[u] = rec[u] = true;
        for (int v : g.get(u)) {
            if (!vis[v] && dfs(v, vis, rec, g)) return true;
            else if (rec[v]) return true;
        }
        rec[u] = false;
        return false;
    }
    public static void main(String[] a) {
        int n = 3;
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        g.get(0).add(1); g.get(1).add(2); g.get(2).add(0); // Directed cycle
        boolean[] vis = new boolean[n], rec = new boolean[n];
        boolean cycle = false;
        for (int i = 0; i < n; i++)
            if (!vis[i] && dfs(i, vis, rec, g)) cycle = true;
        System.out.println(cycle ? "Cycle Found" : "No Cycle");
    }
}

JAVA Output

Input:
Graph Edges: 0→1, 1→2, 2→0 (directed)
Output:
Cycle Found

Python Program

def dfs(u, vis, rec, g):
    vis[u] = rec[u] = True
    for v in g[u]:
        if not vis[v]:
            if dfs(v, vis, rec, g): return True
        elif rec[v]: return True
    rec[u] = False
    return False

n = 4
g = {0: [1], 1: [2], 2: [3], 3: []}  # No cycle
vis = [False]*n
rec = [False]*n
cycle = any(not vis[i] and dfs(i, vis, rec, g) for i in range(n))
print("Cycle Found" if cycle else "No Cycle")

Python Output

Input:
Graph Edges: 0→1, 1→2, 2→3 (directed)
Output:
No Cycle

In-Depth Explanation

Example

In the C program, the graph has the following edges:

0 – 1

|      |

2 —

It's a triangle — a standard undirected cycle. DFS identifies the back edge 2–0, which does not originate from its direct parent.

In the Java example, the directed graph is a loop: 0 → 1 → 2 → 0. Applying a recursion stack (rec[]), we detect the cycle during depth traversal.

Real-Life Analogy

Consider a follow chain on a social network. Alice follows Bob, Bob follows Charlie, and Charlie follows Alice — you're in a loop. That's a cycle.

In project management, if A relies upon B, B relies upon C, and C relies upon A — it's a loop, which stops things from moving forward — precisely what cycle detection is all about.

Why It Matters

Cycle detection is important in:

Compilers (ensure circular imports)

Project planning software (check task dependency chains)

Operating systems (deadlock detection)

Graph theory and topological sorting

Without it, systems can go into infinite loops, crash, or be unsolvable.

Learning Insights

You learn how

DFS (with parent tracking for undirected graphs) detects cycles by identifying back edges

BFS (with parent tracking) can achieve the same iteratively

In directed graphs, you require a recursion stack (rec[]) to identify cycles

It reinforces the idea of graph traversal, cycle conditions, and the distinction between undirected and directed logic.

Interview & Real-World Use

Cycle detection is among the most frequently asked interview questions in:

Graph algorithms

Topological sort prerequisites

Deadlocks or infinite loops detection

Handling DAGs (Directed Acyclic Graphs)

Practical applications in the real world:

Build systems (make, ant, etc.) to identify dependency cycles

Scheduling programs

Checking course prerequisites

AI planning trees

Detection of cycles using DFS and BFS is among the most practical and necessary graph algorithms in computer science. Whether undirected or directed graphs, learning how back edges operate and how to monitor recursion is very important. These brief, effective implementations in C, C++, Java, and Python serve to illuminate the idea in varying situations. This information is regularly put to the test in interviews and applied in real-world applications such as compilers, workflow engines, dependency managers, and operating systems. It becomes the building block for more advanced graph concepts such as topological sort, SCCs, and deadlock detection.