Detect cycle in undirected graph

Detect cycle in undirected graph

Given an undirected graph, find if there is a cycle in that undirected graph. For example, below graph has cycles as 2->3->4->2 and 5->4->6->5 and a few more.

cycle in undirected graph

A simple definition of a cycle in an undirected graph would be: If while traversing the graph, we reach a node which we have already traversed to reach the current node, then there is a cycle in the graph.

How can we detect the above condition? It’s an application of Depth First Search. Do a depth-first traversal of a graph. In depth first traversal, we visit the current node and go deep to one of its unvisited neighbors. If a neighbor of the current node is already visited, that means there is a possibility of a cycle. However, make sure that the already visited neighbor is not the parent of the current node, otherwise, there will be always a cycle of two nodes in an undirected graph.

While depth first traversing a graph, keep track of the nodes which are on the stack at present. If there is an edge from the current node to any one of the nodes which are on recursion stack, we say there is a cycle in undirected graph.

To avoid additional space, we can pass the parent pointer to the recursive call and check if the visited node is the parent.

Detect cycle in undirected graph: implementation


package com.company.Graphs;

import java.util.*;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyList {
    private Map<Integer, ArrayList<Integer>> G;
    private boolean isDirected;
    private int count;

    public AdjacencyList(boolean isDirected){
        this.G = new HashMap<>();
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){

        if(this.G.containsKey(start)){
            this.G.get(start).add(dest);
        }else{
            this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
        }

        if(!this.G.containsKey(dest)) {
            this.G.put(dest, new ArrayList<>());
        }
        //In case graph is undirected
        if(!this.isDirected) {
                this.G.get(dest).add(start);
        }
    }

    public boolean isEdge(int start, int dest){
        if(this.G.containsKey(start)){
            return this.G.get(start).contains(dest);
        }

        return false;
    }

   private boolean isCycleUtil(int u, boolean[] visited, int parent){

        for(int v: this.G.get(u)) {
            if(!visited[v]){
                visited[v] = true;
                return isCycleUtil(v, visited, u);
            }
            else if(v != parent){
                return true;
            }
        }

        return false;
    }


    public boolean isCycle(){
        boolean[] visited = new boolean[this.G.size() + 1];

        for(int i = 1; i < this.G.size() + 1; i++) {
            if (!visited[i]) {
                return isCycleUtil(i, visited, -1);
            }
        }
        return false;
    }
}

The complexity of the DFS approach to finding a cycle in an undirected graph is O(V+E) where V is the number of vertices and E is the number of edges.

Please share if there is something wrong or missing. If you are preparing for an interview, please singup for free interview preparation material.

Related articles
Connected components of a graph
Depth first traversal of graph
Graph representations
Breadth First traversal
Topological sorting