Graph Theory Problem Solving - Session 4 ( Cycle Detection in a graph using 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
  1. Lucius Dungeon ( SPOJ )
  2. Graph Connectivity
  3. Validate the Maze ( SPOJ )
  4. Fix the Pond ( Live Archive )
  5. Gravity ( SPOJ )
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 CODELABS3277

Comments