Things to be discussed here are.

• Some Definition
• Cycles in a Graph
• Cycle Detection in Graph using DFS
• Practice Problem

Some Definition

Before moving towards the discussion of Cycle let us discuss some of the definitions in Graph Theory related to paths.

• Walk: A walk is a “way of getting from one vertex to another”, and consists of a sequence of edges, one following after another. Eg.
• a -> e -> d is a walk of length 2,
• a -> e -> b -> c -> d-> e is a walk of length 5.
• e -> d -> c -> b-> e is a walk which is also a cycle.
• Path: A Walk in which no vertex appears more than once is called a path. Eg.
• a -> e -> d is a path of length 2,
• a -> e -> b -> c -> d-> e is a not a path.
• This is also called a “Trail”.
• More on this we will be discussing in Level 5.

Cycle in a Graph

A cycle in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices. A graph without a cycle is called Acyclic Graph. Here we will be discussing a Depth-first Search based approach to check whether the graph contains cycles or not. Theoretically how we will be detecting the presence of the cycle. To discuss we will use this as an example.

Fig 2. Undirected Graph

• To visit node 3 from 1 we have paths
• 1st Path is 1 -> 3
• 2nd Path is 1 -> 2 -> 3
• In this, we are getting two-path because of ancestor (parent of a parent) relation. Here if we consider 1 to be a parent of 2, and 2 to be a parent of 3 then we are also having a relation 1->3 where 1 is an ancestor of 3 which is known as Back-Edge (If a node is connected to any ancestor directly then that edge is called Back-edge).
• If there is a back-edge then there will be more then one path which suggests that the graph contains a cycle.
• Now let us say that edge (2,3) is not there then the graph would be the tree and for every pair of vertices, we will have only one path.

Cycle detection using DFS

To detect we will simply be using the above concept and checking whether there is Back-Edge is there or not in the graph. If there is a back-edge then there is a cycle else not.

• Algorithm
``````dfs ( source, visited[], adjList, parent){
visited[source] = true;
{
if(! visited[u] ) if(dfs( u, visited, adjList, source ) ) return true;
else if( u != parent ) return true;
}
return false;
}``````

Odd Length Cycle:

If the length of the cycle is odd then we call it an odd-length cycle.

Eg: from fig 1 we have a -> e -> b -> a , is an odd length cycle.

Even Length Cycle:

If the length of the cycle is even then we call it an even length cycle.

Eg: from fig 1 we have e -> d -> c -> b -> e, is an even length cycle.

Implementation of the above-discussed Algorithm

This implementation is for the connected graph, for other change it accordingly.

``````#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;

bool dfs(int source, bool visited[], vector<int> adj[], int parent) {
visited[source] = true;
for (auto u : adj[source]) {
if (!visited[u]) {
if (dfs(u, visited, adj, source)) return true;
} else if (parent != u)
return true;
}
return false;
}

void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
}

bool visited[n + 1];
memset(visited, false, sizeof visited);
bool cycle = false;
cycle = dfs(1, visited, adj, -1);

if (cycle)
cout << "The graph contains Cycle.\n";
else
cout << "The graph doesn't contains cycle.\n";
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}``````

Input:

``````5 5
1 2
1 3
3 4
3 5
4 5``````

Output:

``The graph contains Cycle.``

Practice Problem

That’s all for this article, in the next article we will be discussing Connected Component and Cycle detection using BFS and problems related to them. Before moving to the next session do practice the above problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmers or we can help you ).

If you have some content OR material related to this then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA