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.
@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.
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
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.
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.
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 😁)
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.
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 )
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.
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
@@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
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?
Honestly the best video I have seen on this so far. Other videos did not explain the parent node.
Thanks Brian Keegan :)
Does this code work for non continuous graph?
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.
no
@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.
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
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.
Sir , aap nain kamaaal kr dyaa........... What a Explanation.....!
wouldnt it just stuck in an infinite loop if there is an edge with u v equal
Thanks for the great video!
You're welcome, Greer! :)
3:00 Should you change it to- For any visited vertex
can you please put the proof of correctness of the algorithm .
A great explanation thankfull to you❤
thank you, appreciate the hard work
Nice explanation 👍
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/
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...
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.
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 😁)
What is the output
true if there's a cycle otherwise false
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.
why would you check for 1 again it will move to 2 right?
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 )
your code failed in this case
g = Graph(3)
g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(3, 1)
it checks only for triangles???
i would like also to know
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.
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
No
it will check for any figure if it forms a cycle.
@@akhilvegunta6263 you r late
This is wrong. He is indeed using BFS not DFS, as it was traversing around the neighbor
i also felt that he is using bfs instead of DFS
@@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
@@dylankrejci9965 well BFS uses a queue FIFO while DFS uses stack LIFO. so not the same!
bahut loud video hai🤣