Why there is different algorithm for cycle detection in weighted and unweighted graph? can you please explain intuitively
Why there is different algorithm for cycle detection in weighted and unweighted graph?
hi @sahazeer123, the reason is simple because in undirected graph , if we can reach vertex b from a then we can say with certainty that we can reach a from b. but that’s not the case for directed graph. Now let’s discuss why we need different algo for directed graph . for the case of undirected graph the algo for cycle detection is :-
We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle.
but let’s try to apply the algo for the following graph :-
say , u start your traversal from 0 then u mark visited[0] =true then in one pass u will mark 1 2 and 3 as true. but when you again return to 0 and go for 2 then since visited[2] is already marked as true thus the algo give true as return value i.e cycle exists but u can clearly see that it does;nt form a cycle
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.