How to detect cycle in a directed graph using c programming language? | Sololearn: Learn to code for FREE!
New course! Every coder should learn Generative AI!
Try a free lesson
+ 2

How to detect cycle in a directed graph using c programming language?

Just give an algorithm to find cycle .

8th May 2019, 5:38 PM
Chikku
Chikku - avatar
3 Answers
+ 2
Run dfs on the graph while marking differently visited vertices and current path vertices. If you found while scanning a current path vertex, you have actually found a closed circle. Because the graph is directed, run this again and again until visiting all vertices.
13th May 2019, 7:16 AM
daniel
daniel - avatar
+ 1
I tried by using DFS but...not able to detect cycle for some cases!
13th May 2019, 1:28 PM
Chikku
Chikku - avatar
+ 1
Could you bring a case for example? This algorithm should find a circle, if such exists. Maybe you run the dfs only once?
13th May 2019, 5:00 PM
daniel
daniel - avatar