Given an undirected graph, how to check if there is a cycle in the graph?

Java Algorithm – Detect cycle in an undirected graph

For example, the following graph has a cycle 1-0-2-1.

The time complexity of the union-find algorithm is O(ELogV). Like directed graphs, we can use DFS to detect cycle in an undirected graph in O(V+E) time. We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle. The assumption of this approach is that there are no parallel edges between any two vertices.

detect-undirected-graph-cycle

The program is given in Java program, as follows

Java Programming:

[pastacode lang=”java” manual=”%2F%2F%20A%20Java%20Program%20to%20detect%20cycle%20in%20an%20undirected%20graph%0Aimport%20java.io.*%3B%0Aimport%20java.util.*%3B%0A%20%0A%2F%2F%20This%20class%20represents%20a%20directed%20graph%20using%20adjacency%20list%0A%2F%2F%20representation%0Aclass%20Graph%0A%7B%0A%20%20%20%20private%20int%20V%3B%20%20%20%2F%2F%20No.%20of%20vertices%0A%20%20%20%20private%20LinkedList%3CInteger%3E%20adj%5B%5D%3B%20%2F%2F%20Adjacency%20List%20Represntation%0A%20%0A%20%20%20%20%2F%2F%20Constructor%0A%20%20%20%20Graph(int%20v)%20%7B%0A%20%20%20%20%20%20%20%20V%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20adj%20%3D%20new%20LinkedList%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20for(int%20i%3D0%3B%20i%3Cv%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20adj%5Bi%5D%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20add%20an%20edge%20into%20the%20graph%0A%20%20%20%20void%20addEdge(int%20v%2Cint%20w)%20%7B%0A%20%20%20%20%20%20%20%20adj%5Bv%5D.add(w)%3B%0A%20%20%20%20%20%20%20%20adj%5Bw%5D.add(v)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20recursive%20function%20that%20uses%20visited%5B%5D%20and%20parent%20to%20detect%0A%20%20%20%20%2F%2F%20cycle%20in%20subgraph%20reachable%20from%20vertex%20v.%0A%20%20%20%20Boolean%20isCyclicUtil(int%20v%2C%20Boolean%20visited%5B%5D%2C%20int%20parent)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Mark%20the%20current%20node%20as%20visited%0A%20%20%20%20%20%20%20%20visited%5Bv%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20Integer%20i%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20Iterator%3CInteger%3E%20it%20%3D%20adj%5Bv%5D.iterator()%3B%0A%20%20%20%20%20%20%20%20while%20(it.hasNext())%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20it.next()%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20an%20adjacent%20is%20not%20visited%2C%20then%20recur%20for%20that%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20adjacent%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!visited%5Bi%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(isCyclicUtil(i%2C%20visited%2C%20v))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20an%20adjacent%20is%20visited%20and%20not%20parent%20of%20current%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20vertex%2C%20then%20there%20is%20a%20cycle.%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(i%20!%3D%20parent)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Returns%20true%20if%20the%20graph%20contains%20a%20cycle%2C%20else%20false.%0A%20%20%20%20Boolean%20isCyclic()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Mark%20all%20the%20vertices%20as%20not%20visited%20and%20not%20part%20of%0A%20%20%20%20%20%20%20%20%2F%2F%20recursion%20stack%0A%20%20%20%20%20%20%20%20Boolean%20visited%5B%5D%20%3D%20new%20Boolean%5BV%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Call%20the%20recursive%20helper%20function%20to%20detect%20cycle%20in%0A%20%20%20%20%20%20%20%20%2F%2F%20different%20DFS%20trees%0A%20%20%20%20%20%20%20%20for%20(int%20u%20%3D%200%3B%20u%20%3C%20V%3B%20u%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!visited%5Bu%5D)%20%2F%2F%20Don’t%20recur%20for%20u%20if%20already%20visited%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(isCyclicUtil(u%2C%20visited%2C%20-1))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%20to%20test%20above%20methods%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0A%20%20%20%20%20%20%20%20Graph%20g1%20%3D%20new%20Graph(5)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(1%2C%200)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(0%2C%202)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(2%2C%200)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(0%2C%203)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(3%2C%204)%3B%0A%20%20%20%20%20%20%20%20if%20(g1.isCyclic())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Graph%20contains%20cycle%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Graph%20doesn’t%20contains%20cycle%22)%3B%0A%20%0A%20%20%20%20%20%20%20%20Graph%20g2%20%3D%20new%20Graph(3)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(0%2C%201)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(1%2C%202)%3B%0A%20%20%20%20%20%20%20%20if%20(g2.isCyclic())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Graph%20contains%20cycle%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Graph%20doesn’t%20contains%20cycle%22)%3B%0A%20%20%20%20%7D%0A%7D%0A%2F%2F%20This%20code%20is%20contributed%20by%20Aakash%20Hasija” message=”” highlight=”” provider=”manual”/]

Output:

Graph contains cycle
Graph doesn't contain cycle

Time Complexity: The program does a simple DFS Traversal of graph and graph is represented using adjacency list. So the time complexity is O(V+E)

[ad type=”banner”]