Great video and very nice trace of series of steps applied in Kosaraju's Algorithm. I was reading about it in a text book and I couldn't understand the algorithm completely until I saw this video! thanks a lot.
When we visit a vertex for the 1st time we get the start time of that vertex. But when we get the finish time of a vertex it means that all the edges have been visited. Only then we push a vertex into the stack. I hope this helps. For more clarification pls go through the vide again!!
The number of jumps is important to keep track of to know how costly the path of. Think about it as asking for directions from A to X. And not everything has to have a timing of 1 to it, vert AB could take 1 but AD could take 2. Keeping track of the visited nodes would be important from preventing backtracking. So in that previous example, we see that AB is cheap but BD might not exists and BC to BD will end up costing more than AD (2). That's why we keep track of both visited and the finish time. We give a timing value of n to the stack and then n+1 to the next node because the value of any vertex XY will always be assumed to be greater than 0. This allows us to map the graph in a map object / function AND in the event we are looking for some specific node within a "good enough" timing, we can traverse and do the work that much sooner instead of spending eons looking for the absolute best.
At 9:00 you say 2nd DFS function doesn’t compute finish time unlike first DFS function fillOrder(), but I don’t see computing finish time in fillOrder(), can u pls explain?
Shabnam Banu, Thanks, I got ur point but its understood one. In that case we can say reverse for 2nd function i.e. stack is popped in order of time again. I believe In this algorithm mentioning “time” is unnecessary and misleading. There is no role of time in this algo but stack is filled once a node & it’s all neighbours are visited. Otherwise, we are “linking” time & stack in “every” algorithm where stack is used (that pops up another question if the same solution is achieved by same algorithm but without using stack but some other data structure, in many cases we use stack for convenience, but not mandatory). Mentioning time makes it feel like explicit time computation is mandatory.
where is the path between (0,2) in first graph...... a graph is said to be strongly connected if every vertex is reachable from every other vertex. not for path between every pair of virtex
Saying that every vertex is reachable from every other vertices is same as saying that there is a path between every pair of vertices. Your claim does not actually make sense. Reachabilty in graphs is always acquired through a path. The path between (0,2) is 0->1->2.
When we say reachable , it doesn't mean to be having direct connection . there can be any "n" number of vertices between them but still it should be able to reach in a Directed graph . hope this helps
Very well explained but your class is very poorly designed. You should never fix number of vertex (as you pass 5 here) statically. It’s shud be increasable during run time dynamically. Moreover, did you even compile your code? How do you access *adj with class obj when it’s private member? Pls make your class standard one, which can grow dynamically by using some proper data structure.
Who watches this video after ' Google coding interview with a High School Student' ?
Lmao me
Also me
Me
@@mundi7177 kiskee bare me bat Ho rhi h buddy
Ooops
Great explanation but really hate the audio output. It's got a lot of static and it kinda hurts to be honest but still thank you
Bassam Halabiya with that you find a magical order. In that order you should find the SCCs
Amazing video, clear and concise.
The only issue: why the audio is only on one side, my ear is bleeding.
hahahaa, exactly
Hear it without using earphones🙂
Hoping you got your doctor's appointment on time :P
this came in my exam today, thanks to ur brilliant explanation i was able to complete it quickly bro.. keep up the amazing work 🔥
Out of all videos I saw on YT this the best and the shortest one lol...Thanks
The example walkthrough here is just what I needed. Excellent work. Only thing to note is that all the audio was in the right channel
Just implemented this after listening to your explanation. Very clear and useful!
Great video and very nice trace of series of steps applied in Kosaraju's Algorithm. I was reading about it in a text book and I couldn't understand the algorithm completely until I saw this video! thanks a lot.
Was it the Algorithm design Manual lol
Best explanation on the topic till date !!
This video + subtitles = amazing.
my right ear really enjoyed this video
What is the benifit of involving finish time in this concept?
Does that helped in idea generation?
It willd be helpful, if answered this..
When we visit a vertex for the 1st time we get the start time of that vertex. But when we get the finish time of a vertex it means that all the edges have been visited. Only then we push a vertex into the stack. I hope this helps. For more clarification pls go through the vide again!!
aise hi, sexy lag raha tha!
Great video, just don't listen using headphones. It will pierce your ears and crack your head.
Wait! filling order function follows same algo as Topological sorting!
thnaks exam is in 20 minutes and i jsut understood the concept
It was very helpful, thanks for sharing such kind of lectures.
You switched a long of the directions when explaining strongly connected components?
great explanation brother
Nice, But what is the significance of keeping track of finish time in this algorithm ?
The number of jumps is important to keep track of to know how costly the path of. Think about it as asking for directions from A to X. And not everything has to have a timing of 1 to it, vert AB could take 1 but AD could take 2.
Keeping track of the visited nodes would be important from preventing backtracking. So in that previous example, we see that AB is cheap but BD might not exists and BC to BD will end up costing more than AD (2).
That's why we keep track of both visited and the finish time.
We give a timing value of n to the stack and then n+1 to the next node because the value of any vertex XY will always be assumed to be greater than 0. This allows us to map the graph in a map object / function AND in the event we are looking for some specific node within a "good enough" timing, we can traverse and do the work that much sooner instead of spending eons looking for the absolute best.
Thanks a lot, you saved me for my algorithms and data structures course :D
useful as always, thanks Team GFG
what is the difference bw filling order function and topological sorting?
awesome explanation
My right ear understood the whole concept
Gfg is really a great platform to learn!😊
Really Awesome Explaination.
nice explanation
Is there a reason why we reverse the graph?
Very helpful!
my right ear completely understood , it well explain to my left ear
Great explaination...
great explaination...I really liked it!!!
Fill Order function seems to be topological sorting rather then DFS
At 9:00 you say 2nd DFS function doesn’t compute finish time unlike first DFS function fillOrder(), but I don’t see computing finish time in fillOrder(), can u pls explain?
pushing it to the stack is done in the order of the finishing time . Essentially , top of the stack represents the node with maximum finishing time
Shabnam Banu, Thanks, I got ur point but its understood one. In that case we can say reverse for 2nd function i.e. stack is popped in order of time again. I believe In this algorithm mentioning “time” is unnecessary and misleading. There is no role of time in this algo but stack is filled once a node & it’s all neighbours are visited. Otherwise, we are “linking” time & stack in “every” algorithm where stack is used (that pops up another question if the same solution is achieved by same algorithm but without using stack but some other data structure, in many cases we use stack for convenience, but not mandatory). Mentioning time makes it feel like explicit time computation is mandatory.
Nice explanation
Thanks man, great explanation
not able to distinguish DFS, is this really DFS as the order of nodes visited in DFS are different from this.
Awesome explanation, totally saved me
Hey! That was an amazing explanation.. Thanks alott! :D
very nice explanation
Thanks Harshit!
Thank you so much
Great tutorial thank you
Great explanation!
Thanks Meet Sinojia!
Excellent
Great. I like it very much.
Thank you
Can I get this code in c
thank you sir!
İ didn't get it
well explained.
Thank You. :)
Thanks for the appreciation Nishant :)
nice and informative
Indian squad representing.
Dhanyawad
I thought graph is strongly connected if vertices points to each other. so 0 -> 1 and 1 -> 0. No?
no, bcoz 0,1,2,3 is most strongly than 0,1 and 1,0
cool vid indian man
You forgot to delete your memory
your code aint working for my 5 million lines of vertices
Got it finally with ex
where is the path between (0,2) in first graph...... a graph is said to be strongly connected if every vertex is reachable from every other vertex.
not for path between every pair of virtex
Saying that every vertex is reachable from every other vertices is same as saying that there is a path between every pair of vertices. Your claim does not actually make sense. Reachabilty in graphs is always acquired through a path.
The path between (0,2) is 0->1->2.
When we say reachable , it doesn't mean to be having direct connection . there can be any "n" number of vertices between them but still it should be able to reach in a Directed graph . hope this helps
thanks
You should better learn the defination of "path" first
nice
I don't know why he is rushing with the explanation
To keep the length short of the video. and it's a good idea!!
👍🏻
Very well explained but your class is very poorly designed. You should never fix number of vertex (as you pass 5 here) statically. It’s shud be increasable during run time dynamically. Moreover, did you even compile your code? How do you access *adj with class obj when it’s private member?
Pls make your class standard one, which can grow dynamically by using some proper data structure.
Thnku mam.., sry., sir😅
Please talk slowly😪
Great explanation
Nicely explained
Thank you