Cycle Detection in a graph using Depth First Search ( DFS )

Hi, all welcome to Session 4. Things to be discussed here.

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.

Fig 1: Undirected Graph

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 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 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 back-edge then there is a cycle else not.

Algorithm

dfs ( source, visited[], adjList, parent){

visited[source] = true;

for( auto u: adjList[source])

{

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.

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 programmer 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

Cycle Detection in a graph using Depth First Search ( DFS )

Post a Comment

Contact Form