Detect Cycle in Graph

Cycle refers to a closed path or circuit that visits the same vertex more than once. It means you can start and finish at the same vertex by traversing a sequence of edges in the graph. It’s a closed loop within the graph.

In an undirected graph, a cycle occurs when you can traverse a sequence of edges and return to the starting vertex without retracing any edge.

For example, in an undirected graph, the path A -> B -> C -> A forms a simple cycle.

In a directed graph, a directed cycle is a cycle where the edges have a specific direction, and the sequence of edges forms a closed loop.

A graph that contains at least one cycle is called a cyclic graph.

A graph without any cycle is called an acyclic graph.

A directed acyclic graph (DAG) is a directed graph that does not contain any directed cycles.

Table of Contents

Cycle in Undirected Graph:

#include <iostream>
#include <vector>
#include <unordered_set>

class UndirectedGraph {
public:
    explicit UndirectedGraph(int vertices) : vertices(vertices), adjList(vertices) {}

    void addEdge(int from, int to) {
        adjList[from].push_back(to);
        adjList[to].push_back(from);
    }

    bool isCyclic() {
        std::vector<bool> visited(vertices, false);


        for (int i = 0; i < vertices; ++i) {
            if (!visited[i] && isCyclicUtil(i, visited, -1)) {
                return true;
            }
        }

        return false;
    }

private:
    int vertices;
    std::vector<std::vector<int>> adjList;
//For undirected graphs, a back edge is an edge that leads to an already visited node (excluding the parent).
    bool isCyclicUtil(int v, std::vector<bool>& visited, int parent) {
        visited[v] = true;

        for (const int& neighbor : adjList[v]) {
            if (!visited[neighbor]) {
                if (isCyclicUtil(neighbor, visited, v)) {
                    return true;
                }
            } else if (neighbor != parent) {
                return true; // Back edge detected, cycle found
            }
        }

        return false;
    }
};

int main() {
    UndirectedGraph graph(4);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(2, 0);
    graph.addEdge(2, 3);
    graph.addEdge(3, 3);

    if (graph.isCyclic()) {
        std::cout << "Graph contains a cycle (Undirected)" << std::endl;
    } else {
        std::cout << "Graph doesn't contain a cycle (Undirected)" << std::endl;
    }

    return 0;
}

Cycle in Directed Graph:

#include <iostream>
#include <vector>
#include <unordered_set>

class DirectedGraph {
public:
    explicit DirectedGraph(int vertices) : vertices(vertices), adjList(vertices) {}

    void addEdge(int from, int to) {
        adjList[from].push_back(to);
    }

    bool isCyclic() {
        std::vector<bool> visited(vertices, false);
        std::vector<bool> recursionStack(vertices, false);

        for (int i = 0; i < vertices; ++i) {
            if (!visited[i] && isCyclicUtil(i, visited, recursionStack)) {
                return true;
            }
        }

        return false;
    }

private:
    int vertices;
    std::vector<std::vector<int>> adjList;

//For directed graphs, a back edge is an edge that is pointing to an already visited ancestor. 
    bool isCyclicUtil(int v, std::vector<bool>& visited, std::vector<bool>& recursionStack) {
        visited[v] = true;
        recursionStack[v] = true;

        for (const int& neighbor : adjList[v]) {
            if (!visited[neighbor]) {
                if (isCyclicUtil(neighbor, visited, recursionStack)) {
                    return true;
                }
            } else if (recursionStack[neighbor]) {
                return true; // Back edge detected, cycle found
            }
        }

        recursionStack[v] = false; // Remove the vertex from recursion stack
        return false;
    }
};

int main() {
    DirectedGraph graph(4);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(2, 0);
    graph.addEdge(2, 3);
    graph.addEdge(3, 3);

    if (graph.isCyclic()) {
        std::cout << "Graph contains a cycle (Directed)" << std::endl;
    } else {
        std::cout << "Graph doesn't contain a cycle (Directed)" << std::endl;
    }

    return 0;
}