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

- Lucius Dungeon ( SPOJ )
- Graph Connectivity
- Validate the Maze ( SPOJ )
- Fix the Pond ( Live Archive )
- 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 have some

Thank You

**If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you**).**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

## Post a Comment