# Check if an undirected graph contains cycle or not

Given an connected undirected graph, find if it contains any cycle or not.

For example,

Below graph contains a cycle 2-5-10-6-2

Recommended Read: Types of edges involved in DFS and relation between them

#### Approach 1: Using BFS

When we do a BFS from any vertex v in an undirected graph, we may encounter cross-edge that points to a previously discovered vertex that is neither an ancestor nor a descendant of current vertex. Each “cross edge” defines a cycle in an undirected graph. If the cross edge is `x -> y` then since y is already discovered, we have a path from v to y (or from y to v since the graph is undirected) where v is the starting vertex of BFS. So we can say that we have a path `v ~~ x ~ y ~~ v`. that forms a cycle. (Here `~~` represents one more more edges in the path and `~` represents a direct edge).

## C++

Output:

Graph contains cycle

## Java

Output:

Graph contains cycle

#### Approach 2: Using DFS

Below graph contains a cycle 8-9-11-12-8

When we do a DFS from any vertex v in an undirected graph, we may encounter back-edge that points to one of the ancestors of current vertex v in the DFS tree. Each “back edge” defines a cycle in an undirected graph. If the back edge is `x -> y` then since y is ancestor of node x, we have a path from y to x. So we can say that we have a path `y ~~ x ~ y` that forms a cycle. (Here `~~` represents one more more edges in the path and `~` represents a direct edge).

## C++

Output:

Graph contains cycle

## Java

Output:

Graph contains cycle

The time complexity of above solutions is O(n + m) where n is number of vertices and m is number of edges in the graph.     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂  