Detect Cycle in an Undirected Graph | DSA in C++ - Software Development PDF Download

Introduction

Graphs are fundamental data structures used to represent relationships between objects. In many graph applications, it is essential to detect cycles, which are loops in the graph. Detecting cycles in an undirected graph is a common problem in computer science and plays a crucial role in various algorithms. In this article, we will explore how to detect cycles in an undirected graph using Data Structures and Algorithms in C++.

Understanding Undirected Graphs

Before diving into cycle detection, let's have a brief overview of undirected graphs:

• An undirected graph is a collection of vertices connected by edges.
• In an undirected graph, edges have no direction or orientation.
• Each edge connects two vertices and is represented by a pair of vertices.
• A cycle in an undirected graph is a path that starts and ends at the same vertex, visiting other vertices in between.

Detecting Cycles: Depth-First Search (DFS) Algorithm

To detect cycles in an undirected graph, we can use the Depth-First Search (DFS) algorithm. The DFS algorithm explores all possible paths starting from a given vertex, backtracking when necessary. By keeping track of visited vertices during the traversal, we can identify if there is a back edge, indicating the presence of a cycle.

DFS Algorithm for Cycle Detection

Here's a step-by-step breakdown of the DFS algorithm to detect cycles in an undirected graph:

• Create a graph data structure to represent the graph.
• Initialize an array or hash set to keep track of visited vertices.
• Implement a recursive function for DFS traversal.
• Start the DFS traversal from each unvisited vertex.
• For each vertex visited during traversal, mark it as visited and recursively visit its adjacent vertices.
• If an adjacent vertex is already visited and is not the parent of the current vertex, a cycle is detected.

Code Example

Let's now dive into a code example that demonstrates the cycle detection algorithm using DFS in C++:

#include <iostream>

#include <vector>

using namespace std;

bool hasCycleUtil(vector<vector<int>>& graph, int v, vector<bool>& visited, int parent) {

    visited[v] = true;

    for (int i = 0; i < graph[v].size(); ++i) {

        int adj = graph[v][i];

        if (!visited[adj]) {

            if (hasCycleUtil(graph, adj, visited, v))

                return true;

        } else if (adj != parent)

            return true;

    }

    return false;

}

bool hasCycle(vector<vector<int>>& graph) {

    int V = graph.size();

    vector<bool> visited(V, false);

    for (int v = 0; v < V; ++v) {

        if (!visited[v]) {

            if (hasCycleUtil(graph, v, visited, -1))

                return true;

        }

    }

    return false;

}

int main() {

    int V = 4; // Number of vertices

    vector<vector<int>> graph(V);

    // Add edges to the graph

    graph[0].push_back(1);

    graph[1].push_back(2);

    graph[2].push_back(3);

    graph[3].push_back(0);

    if (hasCycle(graph))

        cout << "Cycle detected in the graph.";

    else

        cout << "No cycle found in the graph.";

    return 0;

}

Explanation

In the code example above, we first define a utility function 'hasCycleUtil' that performs the actual DFS traversal. It takes in the graph, the current vertex (v), the visited array, and the parent vertex ('parent'). The 'visited' array keeps track of visited vertices during the traversal.
Inside the 'hasCycleUtil' function, we mark the current vertex as visited and iterate through its adjacent vertices. If an adjacent vertex is not visited, we recursively call 'hasCycleUtil' on it, passing the current vertex as its parent. This helps us identify cycles.
If an adjacent vertex is already visited and is not the parent of the current vertex, we have found a back edge, indicating the presence of a cycle. In such cases, the function returns 'true', indicating the presence of a cycle in the graph.
In the 'hasCycle' function, we initialize the visited array and then iterate through all vertices of the graph. For each unvisited vertex, we call 'hasCycleUtil' and check if a cycle exists. Finally, we return 'true' if a cycle is detected and 'false' otherwise.

Output

When we run the code example, we get the following output:

Cycle detected in the graph.

The output confirms that a cycle is present in the graph.

Sample Problems

Now that we understand how to detect cycles in an undirected graph, let's try solving a couple of sample problems:

Problem 1: Given an undirected graph, write a function to determine whether it is acyclic or not.

bool isAcyclic(vector<vector<int>>& graph) {

    return !hasCycle(graph);

}

Problem 2: Given an undirected graph, write a function to find the length of the shortest cycle (if any).

int shortestCycleLength(vector<vector<int>>& graph) {

    int shortestLength = -1;

    for (int v = 0; v < graph.size(); ++v) {

        vector<bool> visited(graph.size(), false);

        int length = -1;

        if (hasCycleUtil(graph, v, visited, -1))

            length = findCycleLength(graph, v, visited, v, 0);

        if (length != -1 && (shortestLength == -1 || length < shortestLength))

            shortestLength = length;

    }

    return shortestLength;

}

Conclusion

Detecting cycles in an undirected graph is an important problem in computer science. In this article, we explored how to detect cycles in an undirected graph using the Depth-First Search (DFS) algorithm in C++. We provided a step-by-step explanation of the algorithm, along with a code example and sample problems for practice. Understanding cycle detection in graphs is crucial for building efficient algorithms and solving real-world problems efficiently.