Post
Ask Question

Detecting Cycles in Undirected Graphs

In the graph, we can detect cycles using DFS Below is the implementation and explanation.

class DetectCycleInUndirectedGraph
{
    List<int>[] adj;

    public DetectCycleInUndirectedGraph(int n)
    {
        adj = new List<int>[n];

        for (int i = 0; i < n; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int s, int d)
    {
        adj[s].Add(d);
        adj[d].Add(s);
    }

    public bool IsCyclic()
    {
        bool[] visited = new bool[adj.Length];

        for (int i = 0; i < adj.Length; i++)
        {
            if (!visited[i])
            {
                return IsCyclicUtil(-1, i, visited);
            }
        }

        return false;
    }

    public bool IsCyclicUtil(int p, int s, bool[] visited)
    {
        visited[s] = true;
        foreach (var item in adj[s])
        {
            if (!visited[item])
            {
                if (IsCyclicUtil(s, item, visited))
                    return true;
            }
            else if (item != p)
            {
                return true;
            }
        }

        return false;
    }
}

This C# code defines a class Detect_cycle_in_an_undirected_graph that represents an undirected graph and provides methods to detect if there’s a cycle in the graph.

Class Variables

List<int>[] adj: This is an array of lists that represents the adjacency list of the graph. Each index of the array represents a node in the graph, and the list at each index contains the nodes that are adjacent to it.

List<int>[] adj;

Constructor

(Detect_cycle_in_an_undirected_graph(int n)), This constructor initializes the adjacency list with n empty lists, where n is the number of nodes in the graph.

public Detect_cycle_in_an_undirected_graph(int n)
{
    adj = new List<int>[n];
    for (int i = 0; i < n; i++)
    {
        adj[i] = new List<int>();
    }
}

Method (AddEdge(int s, int d))

This method adds an edge between nodes s and d in the graph. Since the graph is undirected, it adds d to the adjacency list of s and s to the adjacency list of d.

public void AddEdge(int s, int d)
{
    adj[s].Add(d);
    adj[d].Add(s);
}

Method (IsCyclic())

This method checks if there’s a cycle in the graph. It does this by iterating over all nodes in the graph and, for each unvisited node, calling IsCyclicUtil.

public bool IsCyclic()
{
    bool[] visited = new bool[adj.Length];
    for (int i = 0; i < adj.Length; i++)
    {
        if (!visited[i])
        {
            return IsCyclicUtil(-1, i, visited);
        }
    }
    return false;
}

Method (IsCyclicUtil(int p, int s, bool[] visited))

This is a helper method used by IsCyclic. It performs a Depth-First Search (DFS) on the graph from the node, marking nodes as visited as it goes along. If it encounters a node that has already been visited and is not the parent of the current node, it means that there’s a cycle in the graph.

public bool IsCyclicUtil(int p, int s, bool[] visited)
{
    visited[s] = true;
    foreach (var item in adj[s])
    {
        if (!visited[item])
        {
            if (IsCyclicUtil(s, item, visited))
                return true;
        }
        else if (item != p)
            return true;
    }
    return false;
}

Summary

This class provides a way to represent an undirected graph and check if it contains a cycle.

  • Time Complexity : O(V + E)
  • Space Complexity : O(V + E) 


Similar Articles