Detect cycle in an undirected graph | GeeksforGeeks

Explanation for the article: www.geeksforgeeks.org/detect-c...
This video is contributed by Illuminati.

[@BrianKeeganMusic]

Honestly the best video I have seen on this so far. Other videos did not explain the parent node.

[@GeeksforGeeksVideos]

Thanks Brian Keegan :)

[@asadsbhatti]

Sir , aap nain kamaaal kr dyaa........... What a Explanation.....!

[@ionuttrif8378]

I made a function that detect if there is a cycle in a graph using bfs, but i don't know how to make it print the members of the cycle, any tips?

[@ishitamittal1546]

Does this code work for non continuous graph?

[@nitishgupta6802]

Isn't it sufficient to check that if the number of edges in the connected graph is more than n-1 (where n is the number of vertices), then it must have a cycle.

[@evapine2795]

no

[@brkekr]

@Ash Win Yes I totally agree with you, but in the case that E>n-1, that would be a smart move to place an if to check whether it has more than n-1 edges at the very beginning of the function isCyclicUtil.

[@tarekadel7631]

This approach makes assumptions that may not hold true: 1) The graph is connected --> But it could have more than 1 connected component 2) Edges >= Vertices

[@parishapranayraj9978]

can you please put the proof of correctness of the algorithm .

[@greerhanshaw]

Thanks for the great video!

[@GeeksforGeeksVideos]

You're welcome, Greer! :)

[@MushafAli-rc2su]

A great explanation thankfull to you❤

[@kmishy]

3:00 Should you change it to- For any visited vertex

[@parthgupta5058]

wouldnt it just stuck in an infinite loop if there is an edge with u v equal

[@coderbuddy3875]

Nice explanation 👍

[@mohitsoni4925]

It will be better if we also explain why the statement is sufficient enough to justify a cycle in graph. This will help us to not memorise the statement but visualise it.

[@mohammedelhag7565]

thank you, appreciate the hard work

[@shubhammalhotra7244]

For every visited vertex v, if there is an adjacent u. Such that u is already visited & u is not the parent of v. So, cycle in the graph is present/

[@mujtabaamer6542]

What is the output

[@ela2316]

true if there's a cycle otherwise false

[@anirudhreddybasani3555]

Then why didn't we used the same logic for directed graphs..there we've used a recursion stack and here we're just using a parent variable...

[@soumavanag5025]

Anirudh reddy Basani consider the following directed graph and do a dry run: (1,2),(2,3),(1,3) Note: there is no directed edge in undirected graph, so tracking of parent is enough which is not the case in directed graphs.

[@Aditya-pl3xg]

you can all you need to do is run a dfs for each vertex in a loop and that's it. actually this way will cover for case of both the undirected graph (since it'll exit in first iteration itself) and for non-connected graphs too. (but don't tell GfG of this common sense they will write a shitty code full of classes and OOPS on their website that'll confuse everyone 😁)

[@rohitk2629]

Wrong! After backtracking from 1 to 0. 0 will again check its each connected node if its visited or not. since 1 is visited and not parent it will return true.

[@sumanthchakravarthi6853]

why would you check for 1 again it will move to 2 right?

[@brkekr]

Well it does not; because in isCyclicUtil, the first if checks if there is any UNVISITED node, if yes, it recurs from there without evaluating the else if (else if checks if there is a visited children, what you said would be true in case of else-if and if statements swapping places )

[@vaibhavimacherla1603]

it checks only for triangles???

[@LawZist]

i would like also to know

[@KjellBoeije]

It detects a cycle whenever a node has a child node that's already visited, and is not it’s parent. If I'm correct this would work for cycles with any number of nodes.

[@GalibFida]

the cycles in this graph are triangles but they don't have to be cycle of three vertices; a cycle can have any number of vertices and this algorithm will still work

[@akhilvegunta6263]

No it will check for any figure if it forms a cycle.

[@hamidansari9331]

@@akhilvegunta6263 you r late

[@xuantungnguyen9719]

your code failed in this case g = Graph(3) g.addEdge(1, 2) g.addEdge(2, 3) g.addEdge(3, 1)

[@sjrohan4042]

bahut loud video hai🤣

[@jdleanne]

This is wrong. He is indeed using BFS not DFS, as it was traversing around the neighbor

[@kasyapdharanikota8570]

i also felt that he is using bfs instead of DFS

[@dylankrejci9965]

@@kasyapdharanikota8570 this graph is kinda weird in that the way its laid out, BFS and DFS are essentially the same. It's DFS in the sense that each node visited follows directly from its parent, but the organization of this particular graph also means that you are in a sense checking the parent and then all of its children in order. The best way to distinguish from within the context of this video is the fact that the parent of node 4 is 3, whereas in BFS it would be 2. Hope this helps

[@adnanhaque1871]

​@@dylankrejci9965 well BFS uses a queue FIFO while DFS uses stack LIFO. so not the same!