old is gold here there are lot of new TH-camrs just giving solutions for the qouestions where this guy taught the very basic algo of those solution in simplest way a long ago thank you buddy
I spent two hrs just search online try to understand this kinda problem until I saw your video. Thank you so much. U are the only one I saw that really want to explain in detail to us.
I want to thank you for the effort you've put in these videos. I've had a really bad teacher on this topic, but everything makes sense when you explain it.
i spent 1/3 today at work figuring out how to detect cycles in a statemachine. In the end I decided to represent the states and events (transitions) as a graph. My final solution was close to yours but I operate with one stack for explored nodes and if the the neighbor is in there i have a cycle. I think maybe your solution is better because you don't have redundand explorations (ever), but my solution might have redundant traversals. It's not significant for me because the tree only contains 6-40 nodes, but for bigger trees your solution is absolutely better! excellent video :) ty!
Thanks so much for this! I was stuck on a problem for weeks and was out of ideas. This helped me think it through from a different perspective and figure it out. I really appreciate your time and effort in putting these tutorials online.
This code is perfect example of good code quality. At the same time code make sure the system is in consistent state , most of the other youtube videos will leave the color and visited array in inconsistent state.
Awsum Explaination!! Spent hours reading the theory... BUT HERE, problems solved in minutes..... Thanks alot Tushar.. Keep posting... All the best.... !!!
Many thanks for this excellent video. It's by far the best and clearest explanation and demonstration of this problem. The theory from this helped me write in C the functions i needed for my data set. You're a star :)
If we look at your other programs, they use a set called visited and sometimes a stack ( the child nodes which have been processed/explored). I feel instead of introducing new terminologies here, you could use " visited" = grey set, "explored" = black set, with one key difference which is "visited" is wiped clean each time dfs() is called. This will main continuity. And white set is of course all vertices.
Thanks very much! I leave my questions here before find out answers: 1. if there is no cycle, can I use this approach to print out the elements in topological order? How? 2. if there is a cycle, can I use this approach to print out the cycle? How? 3. if there are more than one cycle, can I use this approach to print out all cycles? How?
If you are watching this in lockdown believe me you are one of the rarest species on the earth who are willing to acheive something in life. Many students are wasting their time in watching netflix, webseries, playing games, watching movies, ludo, chatting , etc. NITj student here :)
There is much confusion for directed and undirected graph cycle detection, the code should be same in which we check for a back edge, expect for the fact that Directed graph also detects a back edge bw only two node cycle for this we can simply check neighbour is already visited or not but for Undirected we need to check back edge which ensures there are at least three nodes in a cycle. However what Tushar is explaining here is case for multiple graphs(as in disconnected graphs given as one graph).. This video need not be for Directed G alone, it's for both Directed and Undirected G. Please point out any mistake if you find so!! Thanks Cheers
Just return true in function if you find a back edge and return true all the back and read if function returned true keep collected parent into a collection.
Tushar, I have not that much knowledge about graphs. Here I would like to ask one question : Only two sets is not enough to track of visited or unvisited vertices ? www.geeksforgeeks.org/detect-cycle-in-a-graph/ like this?
But if we deleted the edge of the cycle and it was also the part of some other cycle we will never be able to give the right answer . Deleting an edge can go wrong .
Why not use an enumeration with three states like Unvisited, Visiting and Visited and add a reference of this enumeration on the graph-node object itself. Might be a little more efficient in terms of not using extra space for the three collections. Great explanation though!
this is a rather complicated solution, atleast for me. Why not just keep track of visited nodes and backtrack when we are nowwhere to go at some node? It's much easier.
If you were given input as each node containing their own adjacency list then you could tell that two nodes with the same value are actually different nodes. Otherwise it wouldn't make sense to have the input as a list of edges anyways.
![ตีสิบเดย์ [FULL] | เปิดใจ "อาจารย์ เบียร์ ฅนตื่นธรรม" นักสนทนาธรรมสายดุดัน!](http://i.ytimg.com/vi/vqaBI_mnoDk/mqdefault.jpg)
Hope TH-cam gives a lot of money for your videos because they are priceless:D
This is one of the best videos of explaining concepts on TH-cam, no joke.
This is the best video on this topic. If anybody is reading this. You don't need to search for more!!
old is gold here
there are lot of new TH-camrs just giving solutions for the qouestions
where this guy taught the very basic algo of those solution in simplest way a long ago
thank you buddy
I spent two hrs just search online try to understand this kinda problem until I saw your video. Thank you so much. U are the only one I saw that really want to explain in detail to us.
Couldn't find a better explanation on web than this one. Awesome job Tushar!
I want to thank you for the effort you've put in these videos. I've had a really bad teacher on this topic, but everything makes sense when you explain it.
for every tedious problem, i read through multiple things and final destination always turns out to be your videos. :D
strangely, this is true for me also.
I don't think this is very strange, though.
i spent 1/3 today at work figuring out how to detect cycles in a statemachine. In the end I decided to represent the states and events (transitions) as a graph. My final solution was close to yours but I operate with one stack for explored nodes and if the the neighbor is in there i have a cycle.
I think maybe your solution is better because you don't have redundand explorations (ever), but my solution might have redundant traversals.
It's not significant for me because the tree only contains 6-40 nodes, but for bigger trees your solution is absolutely better!
excellent video :) ty!
Congrats, Roy.
What a good job. The best explanation I've seen so far!
The best explaining video I've found in the internet !
seriously man you are the only youtuber who tells the intuition. Other youtubers just dry run the code of gfg.
This was exactly what I needed. Thank you!
Thank you this was useful . We can even use topological sort done by calculating in-degree to find a cycle
Thanks Tushar, this by far the most clear explanation for this algorithm!!
Thanks so much for this! I was stuck on a problem for weeks and was out of ideas. This helped me think it through from a different perspective and figure it out. I really appreciate your time and effort in putting these tutorials online.
Too good Tushar!! Simplest solution for detecting cycle in directed graphs. 👏🏻
This was very helpful. Clearly explained with example, and is indeed comprehensive. Thanks @Tushar Roy!
Great Job Tushar!!
This code is perfect example of good code quality. At the same time code make sure the system is in consistent state , most of the other youtube videos will leave the color and visited array in inconsistent state.
Greetings from Peru, this video will help me a lot tomorrow in my presentation at the university
Greatest explanation on TH-cam. Thank You very much!
Thank you so very much!!! I finally understand the course schedule leetcode problem because of this video!!
you make Indians proud sir.
Your videos clear all my doubts...thank you
Nicely explained Tushar!
Awsum Explaination!! Spent hours reading the theory... BUT HERE, problems solved in minutes..... Thanks alot Tushar.. Keep posting... All the best.... !!!
Amazing! Thank you for your effort, clean and clear tutorial!
thank you for this clear explanation with passing all steps with details
it was very helpful :)
very nice explanation. Thank you!
Many thanks for this excellent video. It's by far the best and clearest explanation and demonstration of this problem. The theory from this helped me write in C the functions i needed for my data set. You're a star :)
If we look at your other programs, they use a set called visited and sometimes a stack ( the child nodes which have been processed/explored). I feel instead of introducing new terminologies here, you could use " visited" = grey set, "explored" = black set, with one key difference which is "visited" is wiped clean each time dfs() is called. This will main continuity. And white set is of course all vertices.
White set is not necessary. If you have the graph, just DFS from every node as long as it is not already in the black set.
Very lucid explanation Tushar!
your handwriting is amazing!
Thanks very much!
I leave my questions here before find out answers:
1. if there is no cycle, can I use this approach to print out the elements in topological order? How?
2. if there is a cycle, can I use this approach to print out the cycle? How?
3. if there are more than one cycle, can I use this approach to print out all cycles? How?
The DFS approach is not discussed in code, the code accompanying the explanation is a Union Find.
If you are watching this in lockdown believe me you are one of the rarest species on the earth who are willing to acheive something in life. Many students are wasting their time in watching netflix, webseries, playing games, watching movies, ludo, chatting , etc. NITj student here :)
Thanks Tushar, great explanation.
You are borderline amazing
Sometimes I wish I was given the great compliment of being "borderline amazing". But the only thing I get called is "borderline".
@@suspiciousbird487 What are you talking about Lydia?
Excellent presentation :) Loved it!!
There is much confusion for directed and undirected graph cycle detection, the code should be same in which we check for a back edge, expect for the fact that Directed graph also detects a back edge bw only two node cycle for this we can simply check neighbour is already visited or not but for Undirected we need to check back edge which ensures there are at least three nodes in a cycle.
However what Tushar is explaining here is case for multiple graphs(as in disconnected graphs given as one graph).. This video need not be for Directed G alone, it's for both Directed and Undirected G.
Please point out any mistake if you find so!!
Thanks
Cheers
Thank you Tushar, you are the man!
VERY CLEAR AND SIMPLE EXPLANATION :)
cheers this helped me to understand it in much simpler way.
Very good explanation. Thank you
Best explanation.
You, my friend, are GOD.
Very good example and well explained
Awesome tutorial! Thank you so much!!!
Great video, well explained
Thank you. This video is great!
u r doing a great job tushar!...keep going like this...it will be a great benefit for us...! :D
thank u for the videos! 2019 fall!
Which program are you using to display sets and graph in gui? Thanks
Where can I find the code for printing the path? The DFS parent map looks like it was only for illustrative purposes.
Just return true in function if you find a back edge and return true all the back and read if function returned true keep collected parent into a collection.
Yoh wow. That's so simple. Perfect tutorial
Why don't your use adjacency list or matrix to represent graph ?
nice explanation!! thanks.
I like a simplified version where you use just two collections: seen, visiting
Excellent explanation !!
Instead of returning T/F, is there a way to return the verticies in the cycle? (such as a tuple of (4,5,6) ?
thank you Tushar, I realized. Great video.
Still the best in 2020!!!
wonderful explanation
Hey Tushar, would you mind doing a video on heavy-light tree decomposition?
Thank you so much for this video!!
The time complexity will be O(N), where N is the number of nodes in the graph. Space complexity will be O(N).
this looks very similar to using topological sorting to detect cycle, what's the difference?
Why aren’t my professors like him?
* Even though after taking our money*
why introduce the concept of black, white and gray? why not just call them visited, visiting, unvisited sets or something like that?
Real nice video! Thank you!
Thanks..i try to implement this white/gray/black set for detecting the cycle and it works..
Very helpful tutorial ... many thanks...The code takes in a Graph as an input , can i find the code/class for that graph ADT?
Great explanation :)
you are one of the best
thanks for you sharing
Tushar, I have not that much knowledge about graphs. Here I would like to ask one question : Only two sets is not enough to track of visited or unvisited vertices ?
www.geeksforgeeks.org/detect-cycle-in-a-graph/ like this?
+Tushar Roy thanks.
The 2 algorithms for directed and undirected graphs seem so similar, and I cant seem to find the differences
For directed, it's only considered a neighbor if it is an outgoing edge.
But if we deleted the edge of the cycle and it was also the part of some other cycle we will never be able to give the right answer .
Deleting an edge can go wrong .
Thanks for your video!
Thanks for this nice explanation. By the way what's the name of this Algorithm ?
Hello， I would like to know if it is possible to download the package .graph? Cuz some the Vertex type is not recognized .
Thanks
Can this also be used to find the largest cycle in a directed graph?
of course. just continue if you found a cycle, note all cycles and if every node is visited then you just compare the lengths between them
@@philippheller9439 can we use same algorithm for cycle in undirected graph?
Best video
Why not use an enumeration with three states like Unvisited, Visiting and Visited and add a reference of this enumeration on the graph-node object itself. Might be a little more efficient in terms of not using extra space for the three collections. Great explanation though!
Nice 👍
What´s the O() complexity of this algorithm?
great lecture!
this is a rather complicated solution, atleast for me.
Why not just keep track of visited nodes and backtrack when we are nowwhere to go at some node? It's much easier.
Umm isn't just finding visited node twice using dfs will work?
Great job
we can use kosarajus method also?
Heyy Tushar can you please explain this question using dfs and a recursion stack ??
It would be of quite help...
You are awesome!
can we just print the grey set to get the cycle?
How to find all cycles using dfs?
why can't this be done as same as in undirected graph using parent reference and visited set.
if graph contains duplicates it is not possiblle right.
we are not able to put them in set even , if we put them in set we lost one node
If you were given input as each node containing their own adjacency list then you could tell that two nodes with the same value are actually different nodes. Otherwise it wouldn't make sense to have the input as a list of edges anyways.
AMAZING!
really amazing