Counting Cycles in Undirected Graph with DFS

Below is the implementation of Depth's first search to count the no. of cycles with length n in an undirected graph using an adjacency List. This algorithm is also very important from the interview point of view.

Suppose we have the below graph given, and we want to find no. of cycles with length n.

The cycles of length 4 in this graph are 0-1-2-3-0, 0-1-4-3-0, 1-0-3-4-1, and 1-2-3-4-1. So, the method will print these cycles and return the count of cycles, which is 4. Please note that each cycle is counted twice (once for each direction), so the final count returned by the method is divided by 2. Therefore, for this example, the output would be 2.

The DFS starts from vertex 0 (since it’s the first vertex) and explores as far as possible along each branch before backtracking. It keeps track of visited vertices to avoid visiting the same vertex twice. When it finds a cycle of length 4 (i.e., a path that starts and ends at the same vertex and includes 4 edges), it increments the cycle count.

class Graph
{
    int V;
    List<int>[] adj;
    int count = 0;

    public Graph(int V)
    {
        this.V = V;
        adj = new List<int>[V];
        for (int i = 0; i < V; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int src, int dest)
    {
        adj[src].Add(dest);
        adj[dest].Add(src);
    }

    public int Dfs(int n)
    {
        bool[] visited = new bool[V];
        for (int i = 0; i < V - (n - 1); i++)
        {
            DfsHelper(visited, n - 1, i, i);
            visited[i] = true;
        }
        return count / 2;
    }

    void DfsHelper(bool[] visited, int n, int vert, int prev)
    {
        visited[vert] = true;
        Console.Write(vert + " ");
        if (n == 0)
        {
            visited[vert] = false;
            if (adj[vert].Contains(prev))
            {
                count++;
                return;
            }
            else
            {
                return;
            }
        }

        for (int i = 0; i < V; i++)
        {
            if (!visited[i] && adj[vert].Contains(i))
            {
                DfsHelper(visited, n - 1, i, vert);
            }
        }
        visited[vert] = false;
    }
}

int V;: This is the number of vertices in the graph.

List<int>[] adj;: This is an array of lists used to store the adjacency lists for each vertex.

int count = 0;: This is a counter used to count the number of cycles found.

public Graph(int V): This is the constructor for the Graph class. It initializes the number of vertices and creates an empty adjacency list for each vertex.

 public Graph(int V)
 {
     this.V = V;
     adj = new List<int>[V];
     for (int i = 0; i < V; i++)
     {
         adj[i] = new List<int>();
     }
 }

public void AddEdge(int src, int dest): This method adds an edge between two vertices src and dest. Since this is an undirected graph, it adds dest to the adjacency list of src and vice versa.

  public void AddEdge(int src, int dest)
 {
     adj[src].Add(dest);
     adj[dest].Add(src);
 }

public int Dfs(int n): This method performs a DFS on the graph to find all cycles of length n. It initializes a boolean array visited to keep track of visited vertices, then calls the helper method DfsHelper for each vertex. After each call, it marks the current vertex as visited. Finally, it returns the total number of cycles found divided by 2 (since each cycle is counted twice).

 public int Dfs(int n)
 {
     bool[] visited = new bool[V];
     for (int i = 0; i < V - (n - 1); i++)
     {
         DfsHelper(visited, n - 1, i,i);
         visited[i] = true;
     }
     return count / 2;
 }

void DfsHelper(bool[] visited, int n, int vert,int prev): This is a helper method for the DFS. It marks the current vertex as visited and prints it. If n equals 0, it checks if there’s an edge between the current vertex and the starting vertex (prev). If there is, it increments the cycle count. Then it recursively calls itself for all unvisited vertices adjacent to the current vertex. After all adjacent vertices have been visited, it marks the current vertex as unvisited again (backtracking).

void DfsHelper(bool[] visited, int n, int vert,int prev)
{
    visited[vert] = true;
    Console.Write(vert + " ");
    if (n == 0)
    {
        visited[vert] = false;
        if (adj[vert].Contains(prev))
        {
            count++;
            return;
        }
        else return;
    }

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

        if (!visited[i] && adj[vert].Contains(i))
            DfsHelper(visited, n - 1, i, vert);

    }
    visited[vert] = false;

}

• Time Complexity : O(V*V)
• Space Somplexity: O(V )