# 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)