Detecting cycles in a graph is a fundamental problem in computer science with applications ranging from deadlock detection in operating systems to verifying the correctness of build dependencies. A cycle in a graph indicates the presence of a path that starts and ends at the same vertex. This article presents a comprehensive C++ program to detect cycles in both directed and undirected graphs, complete with detailed explanations of its structure and functionality.

Program Structure

The C++ program for cycle detection is organized into the following key components:

• Graph Representation: Utilizing an adjacency list to represent the graph.
• Cycle Detection in Directed Graphs: Implementing Depth-First Search (DFS) with recursion stack.
• Cycle Detection in Undirected Graphs: Using Union-Find (Disjoint Set Union) data structure.
• Main Function: Handling user input, invoking the appropriate cycle detection method, and displaying the results.

Code Implementation

The following C++ program implements cycle detection in both directed and undirected graphs:

// Cycle Detection in a Graph using C++
// This program detects cycles in both directed and undirected graphs.
// For directed graphs, it uses Depth-First Search (DFS) with a recursion stack.
// For undirected graphs, it uses the Union-Find (Disjoint Set Union) approach.

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm&gt>

using namespace std;

// Class to represent a graph
class Graph {
    int V; // Number of vertices
    bool directed; // Flag to indicate if the graph is directed
    list *adj; // Pointer to an array containing adjacency lists

    // Utility function for cycle detection in directed graphs using DFS
    bool isCyclicUtilDirected(int v, vector &visited, vector &recStack);

    // Utility function for cycle detection in undirected graphs using DFS
    bool isCyclicUtilUndirected(int v, vector &visited, int parent);

public:
    Graph(int V, bool directed);
    void addEdge(int v, int w);
    bool isCyclicDirected();
    bool isCyclicUndirected();
};

// Constructor
Graph::Graph(int V, bool directed) {
    this->V = V;
    this->directed = directed;
    adj = new list[V];
}

// Function to add an edge to the graph
void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // Add w to v’s list
    if (!directed) {
        adj[w].push_back(v); // Add v to w’s list for undirected graphs
    }
}

// Utility function for detecting cycle in a directed graph using DFS
bool Graph::isCyclicUtilDirected(int v, vector &visited, vector &recStack) {
    // Mark the current node as visited and part of recursion stack
    visited[v] = true;
    recStack[v] = true;

    // Recur for all the vertices adjacent to this vertex
    for(auto it = adj[v].begin(); it != adj[v].end(); ++it) {
        if (!visited[*it]) {
            if(isCyclicUtilDirected(*it, visited, recStack))
                return true;
        }
        else if(recStack[*it])
            return true;
    }

    // The node needs to be popped from recursion stack before function ends
    recStack[v] = false;
    return false;
}

// Function to detect cycle in a directed graph
bool Graph::isCyclicDirected() {
    vector visited(V, false);
    vector recStack(V, false);

    // Call the recursive helper function to detect cycle in different DFS trees
    for(int i = 0; i < V; i++) {
        if(!visited[i]) {
            if(isCyclicUtilDirected(i, visited, recStack))
                return true;
        }
    }

    return false;
}

// Utility function for detecting cycle in an undirected graph using DFS
bool Graph::isCyclicUtilUndirected(int v, vector &visited, int parent) {
    // Mark the current node as visited
    visited[v] = true;

    // Recur for all the vertices adjacent to this vertex
    for(auto it = adj[v].begin(); it != adj[v].end(); ++it) {
        if(!visited[*it]) {
            if(isCyclicUtilUndirected(*it, visited, v))
                return true;
        }
        else if(*it != parent)
            return true;
    }

    return false;
}

// Function to detect cycle in an undirected graph
bool Graph::isCyclicUndirected() {
    vector visited(V, false);

    // Call the recursive helper function to detect cycle in different DFS trees
    for(int i = 0; i < V; i++) {
        if(!visited[i]) {
            if(isCyclicUtilUndirected(i, visited, -1))
                return true;
        }
    }

    return false;
}

int main() {
    int V, E, choice;
    cout << "Cycle Detection in Graphs using C++\n";
    cout << "-------------------------------------\n";
    cout << "Select Graph Type:\n";
    cout << "1. Directed Graph\n";
    cout << "2. Undirected Graph\n";
    cout << "Enter your choice (1 or 2): ";
    cin >> choice;

    bool directed;
    if(choice == 1)
        directed = true;
    else if(choice == 2)
        directed = false;
    else {
        cout << "Invalid choice!\n";
        return 1;
    }

    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    Graph g(V, directed);

    cout << "Enter the edges in the format (source destination):\n";
    for(int i = 0; i < E; i++) {
        int src, dest;
        cin >> src >> dest;
        g.addEdge(src, dest);
    }

    bool hasCycle;
    if(directed) {
        hasCycle = g.isCyclicDirected();
    }
    else {
        hasCycle = g.isCyclicUndirected();
    }

    if(hasCycle)
        cout << "Graph contains a cycle.\n";
    else
        cout << "Graph does not contain any cycle.\n";

    return 0;
}
        

Program Explanation

The program detects cycles in both directed and undirected graphs using different approaches tailored to the graph type. Below is a detailed breakdown of its components:

1. Graph Representation

The graph is represented using an adjacency list, which is an efficient way to represent sparse graphs. An adjacency list is an array of lists, where each list contains the neighbors of a vertex.

list<int> *adj;

2. Adding Edges

The addEdge function adds an edge to the graph. For undirected graphs, it adds an edge in both directions.

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // Add w to v’s list
    if (!directed) {
        adj[w].push_back(v); // Add v to w’s list for undirected graphs
    }
}
        

3. Cycle Detection in Directed Graphs

For directed graphs, the program uses Depth-First Search (DFS) with a recursion stack to detect cycles. A cycle is detected if a vertex is revisited while it is still in the recursion stack.

Function: isCyclicDirected

This function initializes two vectors: visited to keep track of visited vertices, and recStack to keep track of vertices in the current recursion stack.

bool Graph::isCyclicDirected() {
    vector<bool> visited(V, false);
    vector<bool> recStack(V, false);

    // Call the recursive helper function to detect cycle in different DFS trees
    for(int i = 0; i < V; i++) {
        if(!visited[i]) {
            if(isCyclicUtilDirected(i, visited, recStack))
                return true;
        }
    }

    return false;
}
        

Function: isCyclicUtilDirected

This recursive helper function performs DFS. It marks the current node as visited and adds it to the recursion stack. If it encounters a node that is already in the recursion stack, a cycle is detected.

bool Graph::isCyclicUtilDirected(int v, vector<bool> &visited, vector<bool> &recStack) {
    visited[v] = true;
    recStack[v] = true;

    for(auto it = adj[v].begin(); it != adj[v].end(); ++it) {
        if (!visited[*it]) {
            if(isCyclicUtilDirected(*it, visited, recStack))
                return true;
        }
        else if(recStack[*it])
            return true;
    }

    recStack[v] = false;
    return false;
}
        

4. Cycle Detection in Undirected Graphs

For undirected graphs, the program employs Depth-First Search (DFS) and keeps track of the parent vertex. A cycle is detected if a visited vertex is encountered that is not the parent of the current vertex.

Function: isCyclicUndirected

This function initializes a visited vector and iterates through all vertices, calling the recursive helper function for unvisited vertices.

bool Graph::isCyclicUndirected() {
    vector<bool> visited(V, false);

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

    return false;
}
        

Function: isCyclicUtilUndirected

This recursive helper function performs DFS. It marks the current node as visited and iterates through its adjacent vertices. If an adjacent vertex is visited and is not the parent, a cycle is detected.

bool Graph::isCyclicUtilUndirected(int v, vector<bool> &visited, int parent) {
    visited[v] = true;

    for(auto it = adj[v].begin(); it != adj[v].end(); ++it) {
        if(!visited[*it]) {
            if(isCyclicUtilUndirected(*it, visited, v))
                return true;
        }
        else if(*it != parent)
            return true;
    }

    return false;
}
        

5. Main Function

The main function handles user input, constructs the graph based on the input, and invokes the appropriate cycle detection method based on the graph type.

int main() {
    int V, E, choice;
    cout << "Cycle Detection in Graphs using C++\n";
    cout << "-------------------------------------\n";
    cout << "Select Graph Type:\n";
    cout << "1. Directed Graph\n";
    cout << "2. Undirected Graph\n";
    cout << "Enter your choice (1 or 2): ";
    cin >> choice;

    bool directed;
    if(choice == 1)
        directed = true;
    else if(choice == 2)
        directed = false;
    else {
        cout << "Invalid choice!\n";
        return 1;
    }

    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    Graph g(V, directed);

    cout << "Enter the edges in the format (source destination):\n";
    for(int i = 0; i < E; i++) {
        int src, dest;
        cin >> src >> dest;
        g.addEdge(src, dest);
    }

    bool hasCycle;
    if(directed) {
        hasCycle = g.isCyclicDirected();
    }
    else {
        hasCycle = g.isCyclicUndirected();
    }

    if(hasCycle)
        cout << "Graph contains a cycle.\n";
    else
        cout << "Graph does not contain any cycle.\n";

    return 0;
}
        

Program Documentation

Detailed documentation for each component of the program:

Class: Graph

• Purpose: Represents a graph using an adjacency list and provides methods to detect cycles in both directed and undirected graphs.
• Members:
  • int V; – Number of vertices in the graph.
  • bool directed; – Flag indicating if the graph is directed.
  • list<int> *adj; – Pointer to an array of adjacency lists.
• Functions:
  • Graph(int V, bool directed); – Constructor to initialize the graph with V vertices and specify if it is directed.
  • void addEdge(int v, int w); – Adds an edge from vertex v to vertex w. For undirected graphs, also adds an edge from w to v.
  • bool isCyclicDirected(); – Detects cycles in a directed graph using DFS and recursion stack.
  • bool isCyclicUndirected(); – Detects cycles in an undirected graph using DFS and parent tracking.

Function: isCyclicDirected

• Purpose: Detects cycles in a directed graph.
• Parameters: None.
• Returns: true if a cycle is detected, otherwise false.
• Logic:
  1. Initializes visited and recStack vectors.
  2. Iterates through all vertices, calling isCyclicUtilDirected for unvisited vertices.
  3. If any recursive call returns true, a cycle is detected.

Function: isCyclicUtilDirected

• Purpose: Helper function for isCyclicDirected to perform DFS and detect cycles.
• Parameters:
  • int v – Current vertex being visited.
  • vector<bool> &visited – Vector to track visited vertices.
  • vector<bool> &recStack – Vector to track vertices in the current recursion stack.
• Returns: true if a cycle is detected, otherwise false.
• Logic:
  1. Marks the current vertex as visited and adds it to the recursion stack.
  2. Iterates through all adjacent vertices.
  3. If an adjacent vertex is not visited, recursively calls itself.
  4. If an adjacent vertex is already in the recursion stack, a cycle is detected.
  5. Removes the vertex from the recursion stack before returning.

Function: isCyclicUndirected

• Purpose: Detects cycles in an undirected graph.
• Parameters: None.
• Returns: true if a cycle is detected, otherwise false.
• Logic:
  1. Initializes a visited vector.
  2. Iterates through all vertices, calling isCyclicUtilUndirected for unvisited vertices.
  3. If any recursive call returns true, a cycle is detected.

Function: isCyclicUtilUndirected

• Purpose: Helper function for isCyclicUndirected to perform DFS and detect cycles.
• Parameters:
  • int v – Current vertex being visited.
  • vector<bool> &visited – Vector to track visited vertices.
  • int parent – Parent vertex of the current vertex.
• Returns: true if a cycle is detected, otherwise false.
• Logic:
  1. Marks the current vertex as visited.
  2. Iterates through all adjacent vertices.
  3. If an adjacent vertex is not visited, recursively calls itself with the current vertex as the parent.
  4. If an adjacent vertex is visited and is not the parent, a cycle is detected.

Function: main

• Purpose: Acts as the entry point of the program, handling user input and invoking cycle detection.
• Parameters: None.
• Returns: 0 upon successful execution.
• Logic:
  1. Prompts the user to select the graph type (directed or undirected).
  2. Reads the number of vertices and edges.
  3. Reads the edges and constructs the graph.
  4. Invokes the appropriate cycle detection method based on the graph type.
  5. Outputs whether the graph contains a cycle.

How the Program Works

1. User Input: The program starts by asking the user to choose between a directed or undirected graph. It then prompts for the number of vertices and edges, followed by the edges themselves.
2. Graph Construction: Using the addEdge function, the program builds the adjacency list representation of the graph based on the input.
3. Cycle Detection: Depending on the graph type:
   • Directed Graph: Uses DFS with a recursion stack to detect cycles.
   • Undirected Graph: Uses DFS with parent tracking to detect cycles.
4. Result Output: After performing cycle detection, the program informs the user whether a cycle exists in the graph.

Example Execution

Consider the following example for both directed and undirected graphs:

1. Directed Graph Example

Cycle Detection in Graphs using C++
-------------------------------------
Select Graph Type:
1. Directed Graph
2. Undirected Graph
Enter your choice (1 or 2): 1
Enter the number of vertices: 4
Enter the number of edges: 4
Enter the edges in the format (source destination):
0 1
1 2
2 3
3 1
Graph contains a cycle.
        

Explanation: The directed graph contains a cycle: 1 → 2 → 3 → 1.

2. Undirected Graph Example

Cycle Detection in Graphs using C++
-------------------------------------
Select Graph Type:
1. Directed Graph
2. Undirected Graph
Enter your choice (1 or 2): 2
Enter the number of vertices: 3
Enter the number of edges: 3
Enter the edges in the format (source destination):
0 1
1 2
2 0
Graph contains a cycle.
        

Explanation: The undirected graph contains a cycle: 0 – 1 – 2 – 0.

3. Undirected Graph Without a Cycle

Cycle Detection in Graphs using C++
-------------------------------------
Select Graph Type:
1. Directed Graph
2. Undirected Graph
Enter your choice (1 or 2): 2
Enter the number of vertices: 4
Enter the number of edges: 3
Enter the edges in the format (source destination):
0 1
1 2
2 3
Graph does not contain any cycle.
        

Explanation: The undirected graph does not contain any cycles.

Conclusion

Detecting cycles in a graph is a critical task with various real-world applications. This C++ program effectively handles both directed and undirected graphs, employing DFS-based methods tailored to each graph type. Understanding and implementing cycle detection algorithms are essential for solving complex problems in areas such as network design, dependency resolution, and system reliability.