Brief demonstration and explanation of Strongly Connected Components, this particular graph was copied from another video since i am too lazy to make one up myself :)
Good explanation up until you said "you can kind of tell which are the SCC's". Yes it's obvious, but what about for graphs I can't tell? If I'm writing an algorithm, how can I tell which are the SCC's? You also explained what that the numerator/denominators are for the first graph, but you number the 2nd graph and not explain what the purpose was.
simply wow, I had a quiz on SCC and I haven't any single idea how to solve these problem, then voila found the great video...thanks brother for saving my ass.
You explained a text book solution (algorithm), but failed to communicate where exactly does someone realize when he/she gets a SCC. For ppl who need further explanation - SCC is found on the second traversal, when DFS on a vertex finishes. The number of DFSes provides the number of SCC. In order to arrive at such a state, one has to follow the order of vertices obtained by the traversal of the transposed graph.
absolutely right just keep the post order of reverse graph and write it on actual grapg nodes, do DFS on original graph on the basis of descending post order when dsf end its a scc thanks,
To make sure that if you have an edge say U->V where U and V are connected, then, in the second DFS, U would have finished before the start of V. If we don't make the transpose of the graph, then we cannot be sure of that.
This is hilarious... you spend 12 min to explain an algorithms that finds the SCC and then you find them by yourself? By hand? How is machine supposed to find that? You almost made it but then gave up towards the end...
His explanation is perfect. If you read the book Algorithms by DPV it is exactly how the book explains it. If you just want pseudo codes just go to geeksforgeeks and the link is attached. Stop the hate here thank you so much. www.geeksforgeeks.org/strongly-connected-components/
@@jielyu4943 He does have a point. He should've explained how algorithmically it can be found. You don't even need to draw G Transpose to find it manually.
Terrible explanation. You make us watch the whole video and right at the end when we need to see how they're strongly connected you don't explain that portion lmao. Why did you circle those 4 components???
Thanks. This was much more efficient and understandable than the manner in which this content is usually presented.
perfect! I looked for a lot and your video is the best I've found about strongly coonected components.
Good explanation up until you said "you can kind of tell which are the SCC's". Yes it's obvious, but what about for graphs I can't tell? If I'm writing an algorithm, how can I tell which are the SCC's? You also explained what that the numerator/denominators are for the first graph, but you number the 2nd graph and not explain what the purpose was.
simply wow, I had a quiz on SCC and I haven't any single idea how to solve these problem, then voila found the great video...thanks brother for saving my ass.
Yes I’m learning this topic now and don’t understand the book, I’ve watched many videos, and this is the best.
Recommended to watch at 1.25x speed .
Good explanation by the way
Omg this is the best vdo of strongly connected components after I’ve watched for a few. Thanks so much please create more great content:)
Your mode of explanation is awesome, expecting more videos from your side, keep going..
thank you very much! please keep posting the videos.
You explained a text book solution (algorithm), but failed to communicate where exactly does someone realize when he/she gets a SCC. For ppl who need further explanation - SCC is found on the second traversal, when DFS on a vertex finishes. The number of DFSes provides the number of SCC. In order to arrive at such a state, one has to follow the order of vertices obtained by the traversal of the transposed graph.
absolutely right just keep the post order of reverse graph and write it on actual grapg nodes, do DFS on original graph on the basis of descending post order when dsf end its a scc thanks,
CLRS.
I really love how he explained it in a calm and relaxing way.
What if I go to f from a at 10:18 then b will never be traversed and it would form another SCC
thanks for the video. You explained this tricky topic very well.
Amazing explanation. One question though, do you cross out the letters from the list only when the numerator and denominator are both filled?
Well explained !! Thanks a lot, after seeing so many dumb videos your explanation helped me understand this fucking problem. :)
Very well explained. Thank you
Great.... Awesome tutorial simply understand
thank you :)
Is this method same as kosaraju's algorithm ??
do one where G originally has weighted vertices :3 except that its nice!
Really a good explanation... Really helped me... Thanks 4 this good explanation video... 😃
Can you explain why we need to do transpose of the graph to find the strongly connected component?
To make sure that if you have an edge say U->V where U and V are connected, then, in the second DFS, U would have finished before the start of V. If we don't make the transpose of the graph, then we cannot be sure of that.
Thanks! You help a lot of people. Thank you
Thank you Julio
So, what's a strongly connected component anyway?
Nice Work man!!
Thank you!
great explanation!! helped me a lot!
I agree with kevin, you did not explain how you come to a conclusion of the SCC.
hmm, okay, I ll upload another video on this with more detailed explanation.
@@EducateYourselfNow Or you can just explain by words in the comments.
thanks good job
Are you Swedish?
No i am not
what if tow nods have the same value
that would not be possible right? because they would not be discovered at the same time. What specifically are you referring to?
It's possible when ur starting node say (a) has two paths let say to (b) and (c) then what will be the ordering of positions ?
@@AhsanKhan-eb2zb You just go in alphabetical order. That's the whole idea of topological sorting.
This is hilarious... you spend 12 min to explain an algorithms that finds the SCC and then you find them by yourself? By hand? How is machine supposed to find that? You almost made it but then gave up towards the end...
His explanation is perfect. If you read the book Algorithms by DPV it is exactly how the book explains it. If you just want pseudo codes just go to geeksforgeeks and the link is attached. Stop the hate here thank you so much.
www.geeksforgeeks.org/strongly-connected-components/
@@jielyu4943 He does have a point. He should've explained how algorithmically it can be found. You don't even need to draw G Transpose to find it manually.
please refer to my description
Terrible explanation. You make us watch the whole video and right at the end when we need to see how they're strongly connected you don't explain that portion lmao. Why did you circle those 4 components???