**Objective**: Given undirected graph write an algorithm to find out whether graph contains cycle or not.

**Example**:

**Approach**:

Earlier we have seen how to find cycles in directed graphs. In this article we will solve it for undirected graph. This problem can be solved in multiple ways, like topological sort, DFS, disjoint sets, in this article we will see this simplest among all, using DFS.

**Using DFS (Depth-First Search)**

- Do DFS from every vertex. (please read DFS here).
- During DFS, for any current vertex ‘x’ (currently visiting vertex) if there an adjacent vertex ‘y’ is present which is already visited and ‘y’ is not a direct parent of ‘x’ then there is a cycle in graph.
- Why not parent:
- Let’s assume, vertex ‘x’ and ‘y’ and we have edge between them.
**x—-y**. - Now do DFS from ‘x’, once you reach to ‘y’, will do the DFS from ‘y’ and adjacent vertex is ‘x’ and since its already visited so there should be cycle but actually there is no cycle since ‘x’ is a parent of ‘y’. That is why we will ignore visited vertex if it is parent of current vertex.

- Let’s assume, vertex ‘x’ and ‘y’ and we have edge between them.

**Java Code**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

import java.util.LinkedList; | |

public class UndirectedGraphCycle { | |

static class Graph{ | |

int vertices; | |

LinkedList<Integer> [] adjList; | |

public Graph(int vertices) { | |

this.vertices = vertices; | |

adjList = new LinkedList[vertices]; | |

for (int i = 0; i <vertices ; i++) { | |

adjList[i] = new LinkedList<>(); | |

} | |

} | |

public void addEdge(int source, int destination){ | |

//add forward edge | |

adjList[source].addFirst(destination); | |

//add reverse edge | |

adjList[destination].addFirst(source); | |

} | |

public boolean isCycle() { | |

boolean result = false; | |

//visited array | |

boolean[] visited = new boolean[vertices]; | |

//do DFS, from each vertex | |

for (int i = 0; i <vertices ; i++) { | |

if(visited[i]==false){ | |

if(isCycleUtil(i, visited, –1)){ | |

return true; | |

} | |

} | |

} | |

return result; | |

} | |

boolean isCycleUtil(int currVertex, boolean [] visited, int parent){ | |

//add this vertex to visited vertex | |

visited[currVertex] = true; | |

//visit neighbors except its direct parent | |

for (int i = 0; i <adjList[currVertex].size() ; i++) { | |

int vertex = adjList[currVertex].get(i); | |

//check the adjacent vertex from current vertex | |

if(vertex!=parent) { | |

//if destination vertex is not its direct parent then | |

if(visited[vertex]){ | |

//if here means this destination vertex is already visited | |

//means cycle has been detected | |

return true; | |

} | |

else{ | |

//recursion from destination node | |

if (isCycleUtil(vertex, visited, currVertex)) { | |

return true; | |

} | |

} | |

} | |

} | |

return false; | |

} | |

} | |

public static void main(String[] args) { | |

int vertices = 6; | |

Graph graph = new Graph(vertices); | |

graph.addEdge(0, 1); | |

graph.addEdge(1, 2); | |

graph.addEdge(2, 3); | |

graph.addEdge(3, 4); | |

graph.addEdge(4, 5); | |

graph.addEdge(5, 2); | |

boolean result = graph.isCycle(); | |

System.out.println("is Cycle present: " + result); | |

} | |

} |

**Output**:

is Cycle present: true