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

Depth first traversal of graph

Depth first traversal of a graph

In the last post, we discussed how to represent a graph in a programmatic way using adjacency matrix and adjacency list representation. Let’s discuss now, how to traverse a graph. There are two ways to traverse a graph: Depth First traversal, commonly called DFS and Breadth First traversal, commonly called as BFS.

What is Depth First Traversal (DFS) ?

Depth First search or traversal is a technique in which we go as deep in the graph as possible and explore nodes, that is we move down the graph from one node to another till we can. Once we reach a node where we cannot go further down, we backtrack and move to node one before and so on.
A depth-first traversal of a graph is a very good example to understand how backtracking works.

Let’s see how do we traverse a graph depth first.

  1. Start with node u.
  2. If u is already visited, return.
  3. Mark visited[u] = true.
  4. For all neighbors v of u.
  5. v is now new u, so u=v and go back to step 2
  6. When all neighbors are processed, backtrack to parent of current u.

When we reach at start node S again and there is no edge to be explored at S, that would be the end of traversal.

Let’s take an example and see how it works. Given the graph below, let’s trace how depth first search will go.
depth first traversal of a graph

We start with node(1), and mark it as visited.

depth first traversal

Now, we pick neighbor of node(1), and go down to node(2) and mar it as visited too.
depth first traversal

Next, we move to the neighbor of node(2), which is node(3).

After marking node(3) visited, we move to node(4).
depth first search in graph

Next, we move to node(6). At this point, we have no neighbors to visit from node(6). So, we start backtracking.
depth first traversal

At node(2), we have another neighbor called node(4), however, node(4) is already visited when we went deep from node(3). So nothing happens, we move further back. At node(1), we have neighbor node(5).
Since node(5) is not visited, we mark it as visited.
depth-first-traversal

At this point, there is no node with neighbor not traversed, so end of depth-first traversal.

Depth first traversal : implementation

package com.company.Graphs;

import java.util.ArrayList;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyMatrix {
    private boolean [][] G;
    private boolean isDirected;

    public AdjacencyMatrix(int numNodes, boolean isDirected){
        this.G  = new boolean[numNodes+1][numNodes+1];
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){
        this.G[start][dest] = true;
        if(!isDirected){
            this.G[dest][start] = true;
        }
    }

    public boolean isEdge(int start, int dest){
        return this.G[start][dest];
    }

    private void DFS(int node, boolean[] visited, 
                     ArrayList<Integer> traversal){
        if(!visited[node]){
            traversal.add(node);
            visited[node] = true;

            //Complexity of this loop is O(V * E)
            for(int i=1; i< this.G[1].length; i++){
                if(this.G[node][i]){
                    //This will be called E times (number of edges)
                    DFS(i, visited, traversal);
                }
            }
        }
    }
    public ArrayList<Integer> depthFirstTraversal(){

        boolean[] visited = new boolean[this.G.length];
        ArrayList<Integer> traversal = new ArrayList<>();

        DFS(1, visited, traversal);

        System.out.println(traversal);
        return traversal;

    }
}

The complexity of the above implementation is O(V * E).

Depth first traversal when the graph is represented using adjacency list.

package com.company.Graphs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

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

    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)));
        }

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

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

        return false;
    }


    private void DFS(int node, boolean[] visited, 
                     ArrayList<Integer> traversal){
        if(!visited[node]){
            traversal.add(node);
            visited[node] = true;

            this.G.get(node).forEach(v -> DFS(v, visited, traversal));
        }
    }
    public ArrayList<Integer> depthFirstTraversal(){

        boolean[] visited = new boolean[this.G.size()+1];
        ArrayList<Integer> traversal = new ArrayList<>();

        DFS(1, visited, traversal);

        System.out.println(traversal);
        return traversal;

    }
}

The complexity of the above implementation is O(V + E).

Both above implementations are recursive implementation. We can use a stack to replace recursion. Algorithm remains the same, for each node visited, put all the adjacent nodes into the stack. Take next node from the stack, mark it as visited and put all the adjacent nodes to stack. Repeat the process till stack is not empty.

public ArrayList<Integer> depthFirstTraversalNonRecursive(){

        boolean[] visited = new boolean[this.G.length];
        ArrayList<Integer> traversal = new ArrayList<>();

        Stack s = new Stack();
        s.push(1);
        visited[1] = true;

        while(!s.isEmpty()){
            int currentNode = (int)s.pop();
            traversal.add(currentNode);

            for(int i=1; i< this.G[1].length; i++){
                if(this.G[currentNode][i] && !visited[i]){
                    s.push(i);
                    visited[i] = true;
                }
            }
        }

        System.out.println(traversal);
        return traversal;

    }

This implementation of dept first traversal or DFS works only if the graph has only one connected component. If there are multiple connected components in the graph, this will not work. For example, above implementation will not work for below graph.

It can be easily fixed. All we need to do is that we try to start DFS from each node of the graph. Check if a node is not already visited for earlier DFS run, then start another DFS from that node. Below is the changed code.

  private void DFS(int node, boolean[] visited, 
                   ArrayList<Integer> traversal){
        if(!visited[node]){
            traversal.add(node);
            visited[node] = true;

            for(int i=1; i< this.G[1].length; i++){
                if(this.G[node][i]){
                    DFS(i, visited, traversal);
                }
            }
        }
    }
    public ArrayList<Integer> depthFirstTraversal(){

        boolean[] visited = new boolean[this.G.length];
        ArrayList<Integer> traversal = new ArrayList<>();

        for(int i=1; i<this.G.length; i++) {
            if(!visited[i])
                DFS(i, visited, traversal);
        }

        System.out.println(traversal);
        return traversal;
    }

Applications of DFS

  1. Minimum spanning tree
  2. To check if graph has a cycle.
  3. Topological sorting
  4. To find strongly connected components of graph
  5. To find bridges in graph

Please share if there something wrong or missing. Please reach out to communications@algorithmsandme.com if you need personalized coaching for an interview.

Graph representations

Graphs representation

Before understanding graph representation in computer languages, let’s understand what is a graph? A graph is collection of edges E : {e1,e2,33…..en} and vertices V : {v1,v2,v3…vn}.
Mathematically, graph is represented as G = (V,E). An edge is pair of vertices (vi, vj) where i,j<=n and vertices are the nodes at the two ends of edges.

Below is an example of a graph, where vertices are (1,2,3,4,5,6) and edges are [ (1,2), (1,4), (2,3), (3,5), (5,4), (4,6) ]

graph-representation

There are two types of graphs in general: directed and undirected. The graph you saw in the above example is a directed graph.
A directed graph is where an edge is one way from one vertex to another, whereas the undirected graph has two-way edges, that is, there is no arrowhead at the end of the edge. In representations, if there is an edge from vertex x to vertex y, in an undirected graph, there will be an edge from vertex y to vertex x.

Graphs representations

There are two ways to represent graphs in programming constructs: adjacency matrix representation and adjacency list representation. Based on the need of algorithm and problem at hand, we decide which way to represent a graph. There are three criteria, which are used to evaluate any representation of a graph.

  • How much space a particular representation will take?
  • How much time it will take to find if a given edge exists in the graph?
  • How long will it take to find all the neighbors of a particular node?
  • Adjacency matrix representation of a graph

    In this representation, we use two dimensional array or matrix G. G(i,j) is set to true if there is an edge between vertex i and vertex j.

    The advantage of the adjacency matrix representation of a graph is that it is very simple to implement. However, when the number of edges between vertices is sparse, a lot of cells in array or matrix remain empty.

    The complexity of graph algorithms is measured in terms of E and V where E is the number of edges and V is the number of vertices.
    In adjacency matrix representation, memory used to represent graph is O(v2). If the graph is undirected then when there is an edge between (u,v), there is also an edge between (v,u). So transpose of the adjacency matrix is the same as the original. So we can save half the space when representing an undirected graph using adjacency matrix. Moreover, if there are no weighted edges in the graph, instead of using one byte, we can use one bit to indicate an edge.
    To determine if a given edge (u,v) is present, we have to look at G[u][v], if it is true, then there is an edge else not. Time complexity is O(1). To find all the neighbors of a node, we have to scan the entire row, which leads to complexity of O(n).

    Adjacency matrix representation of the graph shown above will be:

    adjacency matrix
    adjacency matrix representation of graph

    Adjacency matrix implementation of graph

    package com.company.Graphs;
    
    /**
     * Created by sangar on 21.12.18.
     */
    public class AdjacencyMatrix {
        private boolean [][] G;
        private boolean isDirected;
        
        public AdjacencyMatrix(int numNodes, boolean isDirected){
            this.G  = new boolean[numNodes+1][numNodes+1];
            this.isDirected = isDirected; 
        }
        
        public void addEdge(int start, int dest){
            this.G[start][dest] = true;
            if(!isDirected){
                this.G[dest][start] = true;
            }
        }
        
        public boolean isEdge(int start, int dest){
            return this.G[start][dest];
        }
    }
    
    

    Tests

    package test.Graphs;
    
    import com.company.Graphs.AdjacencyMatrix;
    import org.junit.jupiter.api.Test;
    
    import static org.junit.jupiter.api.Assertions.assertEquals;
    
    /**
     * Created by sangar on 21.12.18.
     */
    public class AdjacencyMatrixTest {
        @Test
        public void createGraphTest() {
    
            AdjacencyMatrix tester = new AdjacencyMatrix(5,false);
    
            tester.addEdge(1,5);
            tester.addEdge(3,4);
            tester.addEdge(2,4);
            tester.addEdge(1,3);
            tester.addEdge(3,5);
            tester.addEdge(5,2);
    
            assertEquals(true, tester.isEdge(3,4));
            assertEquals(false, tester.isEdge(1,4));
    
        }
    }
    
    

    Adjacency list representation of graph

    In adjacency list representation, we have a table of all vertices of the graph. Each entry in that table will have the list of neighbors which this vertex is connected to.
    Space required for adjacency list representation of the graph is O(V +E).
    To find if there is an edge (u,v), we have to scan through the whole list at node(u) and see if there is a node(v) in it. In the worst case, it will take O(E) time, where E is the maximum number of edges in the graph.
    To find all the neighbors of a node, it is just returning all the nodes in the list, which is again of O(E) time complexity.

    Adjacency list representation can be easily extended to represent graphs with weighted edges. Each node contains another parameter weight. For the edge, (u,v)  node in adjacency list of u will have the weight of the edge.

    Above graph can be represented in adjacency list as

    adjacency list graph representation
    adjacency list representation of graph

    Adjacency list implementation

    package com.company.Graphs;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * Created by sangar on 21.12.18.
     */
    public class AdjacencyList {
        private Map<Integer, ArrayList<Integer>> G;
        boolean isDirected;
    
        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)));
            }
    
            //In case graph is undirected
            if(!this.isDirected) {
                if (this.G.containsKey(dest)) {
                    this.G.get(dest).add(start);
                } else {
                    this.G.put(dest, new ArrayList<>(Arrays.asList(start)));
                }
            }
        }
    
        public boolean isEdge(int start, int dest){
            if(this.G.containsKey(start)){
                return this.G.get(start).contains(dest);
            }
    
            return false;
        }
    }
    
    

    Tests

    package test.Graphs;
    
    import com.company.Graphs.AdjacencyList;
    import org.junit.jupiter.api.Test;
    
    import static org.junit.jupiter.api.Assertions.assertEquals;
    
    /**
     * Created by sangar on 21.12.18.
     */
    public class AdjacencyListTest {
        @Test
        public void createGraphTest() {
    
            AdjacencyList tester = new AdjacencyList(false);
    
            tester.addEdge(1,5);
            tester.addEdge(3,4);
            tester.addEdge(2,4);
            tester.addEdge(1,3);
            tester.addEdge(3,5);
            tester.addEdge(5,2);
    
            assertEquals(true, tester.isEdge(3,4));
            assertEquals(false, tester.isEdge(1,4));
    
        }
    }
    

    Quick follow up question: Given a densely connected graph, there will be millions of queries to find if there is an edge between two vertices, which representation is best suited for this use case?
    The first hint is that it is densely connected graph, so there would not be much difference in space used in case of both representation. Finding if there is an edge between two nodes is O(1) operation in adjacency matrix representation whereas it O(E) operation in adjacency list representation. So, in this use case, we would choose the adjacency matrix representation.

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