Tarjans strongly connected components algorithm
Вставка
- Опубліковано 25 сер 2024
- This lecture explains the Tarjans algorithm for finding the strongly connected components in a graph.The previous video explained the same using kosaraju algorithm and link for that is given below.In the tarjans algorithm, we can find all the strongly connected components in just a single traversal of graph.In this video, I have first explained the concepts required to completely understand the reasons behind each step of tarjan's algorithm and then i have shown the dry run example.I have also shown the reason for using low and disc (discovery) time of nodes and how to calculate it with intuition.At the end of the video, I have shown the CODE walk through of this algorithm.This algorithm makes used of Arrays,Stack and a DFS traversal.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
USEFUL VIDEOS:-
Kosaraju Algorithm: • Kosaraju Algorithm | S...
At 19:50 , If you are confused why only single back-edge is allowed ?
Ans-> We are allowed to have a single back-edge only for calculating low and disc. However, It will have a cascading effect at the given time. If you carefully run the algorithm as dry run then you will find only 1 head node of SCC and hence, there will be only 1 SCC. I hope you got it :)
After watching the video I also find it really confusing, I am not sure but what I think is that (6 and 2) has a back edge relation where we need to check if 6 is part of earlier SCC and also that we know that it's articulation point too, and if we take (2 and 0), for 2 to be part of that SCC there no need to check for the back edge. SO I think min(low[u], disc[v]) is for back edge and articulation point. Hope I am not wrong. : )
@@Góne-y2s Yes right. For tree edge, it will be low(v)
this Algorithm has much application- one you mentioned is SCC, then Bridge and Articulation Point. Though all three are the same thing. first asks for a number of components, 2nd is for critical edges and 3rd is for articulate points.
@@techdose4u True for tree edges and only while tracking back and popping from stack.
@@Góne-y2s you are going deep 🙏🏼 😅 great
this is, in my opinion, THE MOST COMPREHENSIVE explanation of Tarjan's algorithm on SCC. The video contained a huge amount of information but it was delivered in a way that was very easy to follow.
👍
Outstanding video from tech dose 🔥🔥🔥🔥🔥🔥
This is so good. Very well explained. This is implementation with understanding and not just memorising an algorithm. I did not understand this in striver's video. I tried hard, but this one, just 1 go, and I could code it. Beautiful!
Thank you so much for this amazing explanation and readable code. Can't believe this is for free.
Welcome :)
What a great video. Finally, I am able to understand this concept. I can see the efforts you made. Thank you :)
Thanks :)
This is such a great explaination of concepts and the algorithm .The code was so intuitive and beautiful . We are so grateful you made this video . Thank you so much !!♥
Welcome 😀
One of the best explanation that anyone can provide. OP Surya🔥
I have been following your entire graph playlist since 1 week and they have been super useful to me. This one was awesome 👌👌. Keep up the good work 👍💯
Thanks ☺️
2 hrs lage ye video smajhne me but ab Confidence aagya is algo me, thanks bhaiya
Welcome :)
you are literally great, literally whenever I did not understand any concept, and then I see your video then all concepts are clear, Thx for such wonderful videos.
Welcome :)
I m regreating why I hadn't come to this channel before, love your explanation. Thanks for helping us🙏
Thank you so much for making it so clear. This algorithm appears to be very hard but your hard work and awesomeness are just great enough to defeat that hardness. Keep it up sir.
Thanks :)
Took me a lot of time to understand from other sources, but able to understand in one watch here. Excellent explanation. Very easy to understand call stack and how to deduce this algorithm. Great job, thank you!
Nobody can explain better than you! Thank you...
Welcome 😁
At first sight, the lecture looked lengthy and boring but it turned out to be the most amazing and simplified explanation of Tarjan's.
Thank you for this lecture.
Thank you very much for the clear explaination...everything is so clear after this video
best explanation of Tarjan's Algorithm . Thank you
Welcome :)
Students of JU are proud of u sir , keep up your work
At 19:50 why are we allowed only single back-edge?
No, you can take the low value at both the step. He has explained it wrong. In that example, you can clearly go from any vertex to any other vertex. They all will account for 1 SCC. As per his algo you will have 2 SCC which is wrong.
I agree, this implementation of having only one back edge is wrong. We can have multiple backedges. It is quite evident from the given graph example that it's a single SCC. I tried the same graph with Kosaraju that's giving me only one SCC. I tried the same graph on GFS's implementation for Tarjans that's also giving a single SCC.
We are allowed to have a single back-edge only for calculating low and disc. However, It will have a cascading effect at the given time. If you carefully run the algorithm as dry run then you will find only 1 head node of SCC and hence, there will be only 1 SCC. I hope you got it :)
Explanation is very nice in the entire youtube, I explored alot, but didn't get this type of explanation. and Finally I understand low, disc why we take that ? , each and every concept. it takes me 2 hrs continuously to understand, in every minute , stopped the video and understand the words more focusly and writing on copy, rather it take me time 2 hr, but understanding the algorithm is more important.
Initially I thought graph algorithms are really easy. Then I came across Tarjan's algorithm😭
😅
Okay let's assume you are sitting in cluster of people and you are connected anticlockwise. Assign number to each person 1,2,3 since you are in cycle eventually you will meet min number. Now think you have clusters of those cycle
@@abhisheksaraf2616 thanks bhai!! 👌👌
@@abhisheksaraf2616 didn't get!
@@akashkumarbeniwal4875 think about cycle in undirected graph if you try to remove any edges or node will it be more than 2 component ans is no now think about a graph with no cycle
Awesome. I understand from the first try. I really recommend this channel!
What a coincidence! This morning I was learning this topic! Many thanks for the video.
Welcome :)
I'm wondering how much efforts u've pushed to make this video. Tysm 🙏🙏🙏
Welcome :)
It's a great video. You explained a very tough concept in such a simple way. Thank You so much Sir.
Welcome :)
thankyou so much sir, you nailed it
Welcome 😊
this is the best UA-cam Channel for CS by far, Good Job brother
Great Explanation sir.
Thanks :)
Huge respect for such explanation
Thanks :)
Excellent sir..! Thanks a lot..!
Tech Dose is God!
So good explaination. Finally understood this algo!.
Very well and indepth explanantion
Great explanation
Thanks :)
Top high quality video about computer science graph theory, others I have looked can't compare with yours.
By watching your video, I can truly understand the content from [Geeks for Geeks] and wiki.
Now I am confident, thank you so much.
Welcome :)
Perfect explanation!!
Thanks :)
Was waiting for this. Thanks so much!!
Welcome :)
The dry run really makes it very clear.
:)
Your videos for graph is awesome.. great job 👏
Thanks :)
Nice explained 👍👍
Thanks
great explaination
Thanks for all the hard work.
Best explanation
Thanks
@@techdose4u This algorithm will help in solving many questions, thanks for ur effort in explaining it :)
thank you sir. It was helpful
At 19:47, explanation is that we cannot min low[u] with low[v], it must be disc[v] since 0 is not directly reachable from 6. But for the given graph, even if we consider low[v] instead of disc[v], answer is there is only 1 strongly connected component isn't it? Will there be any case where taking low[v] for back edge yields wrong result. I couldn't think of any. Please let me know if there is such a graph where it yields wrong result
You are right, using low instead of disc will not yield the wrong result.
kya bat hai,too good
I loved how he changes pen colour at 32:40
Very detailed explanation,thank you sir🙏
Hats off to you sir ! Mind blowing job with this video 🔥💯👌
This is THE BEST!! Thanks a ton!!!!!!
Welcome :)
@@techdose4u I had one doubt. The diagram at 19:45, how many strongly connected components are there? I think the entire graph is strongly connected. Is that correct? If yes, then while updating node no. 6, why can't the low value be 0? because we can reach 0 from 6 and in some youtube videos they said that the scc nodes will have same low-link value.. please clarify
@@prernasingh564 ohh,,, good question. kaha tk kr chuki be 4 mahine me..
Caught ya!!
@@prernasingh564 reply fast if u get notified for me comment, else u wont be alive if u meet ever again
lol!!
@@prernasingh564 After watching the video I also find it really confusing, I am not sure but what I think is that (6 and 2) has a back edge relation where we need to check if 6 is part of earlier SCC and also that we know that it's articulation point too, and if we take (2 and 0), for 2 to be part of that SCC there no need to check for the back edge. SO I think min(low[u], disc[v]) is for back edge and articulation point. : )
Thank you Bhaiya
Great video!, so easily taught!
Thanks
Very Nice Explanaton. Keep making videos
Your videos are great, mate!
Superbly explained.Mind blowing bro ❤️❤️
Great video 😇 really 💞. Thanking you so much sir 😊 to making always very helpful video.
Welcome :)
Thank you so much sir
Welcome :)
Amazing video, Appreciate the effort
Thanks 😊
Tech Dose. what is the significance of FORWARD EDGE in Tarjans algorithm ? I understood the roles played by Tree Edge ( for DFS) / Cross Edge (Ignore) and Back Edge ( update low time based on discovery tiime). And also after back track of tree edge traversal we update low time. Forward edge effectively plays the role of back/cross edge depending on presence/absence of its value in stack ?
I found this explanation better than That of William Fiset, that one regarding the use of low vs index
For all those who are wondering why we used low[u] = min(low[u], disc[v]) for back edge, what I think is that if you look at example given at 18:29 you see that from 6 we have back edge to 2 , so let's say if there was an edge from 6 to 5 then only we could say that 0 is lowest node 6 can visit and the component is connected to other component but here only 2 is lowest node 6 can visit. If we will take more than one back edge may be we would mistakenly take cross edges as back edge also.. For current situation we can only take decision for 2 that it part of our component. May be in future when we explore more nodes 0 also becomes part of our scc. I hope it makes sense !!
Thanks!
Bow down to the master
😂
appreciate your work!!
Thanks :)
Pure Gold
:)
Well explained video!
Thanks
Picture perfect my man
Quality vid. Thanks
Welcome
Nice video as always. Hope you will do more videos about System Design too in the future.
Kosaraju is much more easier than this to implement , but you have explained this really well, thank you
This one is more effective.
CAUTION EVERYONE!!! at @19:24
he has suggested not to take low value for multiple back edges. In fact, one must take it because a low value denotes the min vertex one can reach for a given vertex. In that example he has explained it wrong. You can clearly go from any vertex to any other vertex. They all will account for 1 SCC. As per his algo you will have 2 SCC which is wrong.
Exactly what I was looking for!!! I had the same query. Thanks for clarifying. I also believed that it's a 1 SCC.
so for all cases we take min(low , low) and not min(low , disc) right
How can you say that his algo is resulting 2 SCC.
In fact, no. of SCC = (no. of such node that have " low Val == disc Val")
After processing graph.
Now tell me no. of SCC by his algorithm.
You are getting it wrong, if you dry run the algo yourself, you will understand. His algo will result in only 1 scc. At each step of backtracking we will check if low[v]==dis[v] if so then it will be the head of an scc.
@@arpanbanejee5143 yeah.. I found the mistake I made at that time. Thanks..
I stupidly started doing this on a bi-directional graph and got freaked out when every edge became a back edge LOL.
Sir, I didn't make the stack. I updated only low value and discovery. After completing the traversal, I made a unordered_map and whose low values are same put them into the same key.
But my answer is wrong. I am not getting what is wrong in this.
You did not explain what would happen in the case of a forward edge. I think that forward edges will be treated similar to the cross edge in the algorithm implementation. Is that right?
I have a doubt at 19:50, why are we not allowed to have multiple back edges? The reason provided by @TECH DOSE isn't clear :((
Any help would be appreciated.
Ok but I am still unable to process when are we using the 1st formula [min(low(u), low(v)] and when are we using the 2nd formula [min(low[u], disc[v])]
For me, when I submitted following condition for back edge on gfg as mentioned in the video :
low[u] = Math.min(low[u],disc[v]);
it did'nt pass all test cases.
low[u] = Math.min(low[u],low[v]);
With this condition it worked perfectly fine.
Good description of tarjans algo but I found a little inconsistency. While backtracking why are you waiting to change the Instack to false. I feel like that should be immediately changed to false after we complete exploring and not waiting on finding a SCC. It kind of contradicts what you explained at 12:05.
Thank you for the amazing explanation! I wrote and executed the code in GFG and it worked BUT when I wrote low[u] = min(low[u], low[v]) FOR THE BACK EDGE, IT ALSO WORKED! Can you please give one example (not from the video) to help us know why we are using disc instead of low?
Yeah, I had the same doubt.
Will you please explain why we just check for the discovery value of ancestor and don't consider parent for updating low value of a node?
I think I had explained this in the video. Please rewatch and let us know if you don't get it.
what happens if your graph has multiple parts that are not connected at all?
Can anyone give exmaple where low[u] = min ( low[u], low[v] ) { in back edge case} fails ? 19:50
Please read the pinned comment. Try to dry run. It will work.
why for every discovered node, you are checking only for backedge and cross edge, if it is not backedge why it cant be forward edge?
Will the forward edge change anything you your calculation ? Low will still be the same. Only the discovery time for the nodes skipped will be different but it doesn't matter. Dry run this and check.
@@techdose4u yes, right, but how do we check if it is a cross edge or forward edge if not backedge
@@ankithreddyadudodla7673 no need to check forward edge
@@techdose4u yes, I do know, but in general I am asking
@@ankithreddyadudodla7673 tell me a use case for it :)
Where to practice graph questions from??which is best one??
Leetcode or geeksforgeeks
At 30:21 the edge from 4 to 6 is said to be cross edge but isn't it forward edge?
You are GOD!!
😅
At 15:43, the example looks like 1 strongly connected component right? Am I correct? As each node can be reached from any other node.
If yes, how can we know? as there are 2 lows (0 and 1) after the algo finishes at 20:29.
(0,0) (1,0) (2,0) (5,0)
(3,1) (4,1) ( 6,1)
Nice video
Can we solved it using iteration?
Thanks
Welcome :)
According to wiki a strongly connected means Every node can visit every other node which is TRUE for 19:50 graph so the ans should be 1 but according to u it is 2
What is ur definition of strongly connected graph
Amazing explanation! thanks much!
Can you also tell me what setup you are using for making this video ? Which tablet and software you are using for drawing/writing ? I wanna build similar setup for daily day conference videos.
exccellent
Thanks 😊
Your definition of cross edge is bit different than the actual definition of the cross edge. In your definition, you consider a cross edge from u to v if v is not present in the stack. However, this stack is not the same as the dfs call stack. For eg: take the follow adj list representation of a graph:
1: 2
2: 3, 4
3: 1
4:3
Start dfs from node 1. 1->2, 2->3, 3->1 (back edge), backtrack to 3 , backtrack to 2, 2->4, 4->3 (this should be cross edge, because 3 will not be in dfs call stack, however, it will be in the stack variable that you used in the code. Hence, by your code's definition, this is not a cross edge).
Please, let me know if my understanding is correct or not? I got a bit confused due to this. Thanks.
Ok. I found on wikipedia that we don't remove a vertex from the stack when we backtrack from that node to its parent node. So, although 4->3 is technically a cross edge by original definition, but in this algorithm, we will consider it as a "back edge".
Another confusion that I had was why are we using the disc(v) to update low(u) when there is a back edge from u to v, we can use low(v) as well. Turns out that it does not matter. The result will be the same. However, using using disc(v) is "more" correct in the sense that it disc(v) represents the earliest node reachable from u.
in 12:47 how you gonna know that 0 already present in a stack , we cant access 0 until we pop all elements from stack ?
Can Someone please explain what is low. Am not able to figure it out and its assignment!!
In case of back edge why are we doing low [u] = min(low[u], dis[v]) and not low [u] = min(low[u], dis[u]) . This was my biggest doubt after seeing articles from different sites. Thanks a lot for addressing this .
I thought you were asking me 😅 Okay you just edited the comment I guess.
At 12:00, if I take right edge first and the left edge, then 5->3 would be tree edge and not cross edge as node 3 would not be visited before. Am I wrong?
at 15:17 can anyone show me an example of such graph as the one talked about in the note
Sir, I dint understand what was the use of doing min(low[u],disc[v]) for back edge instead of min(low[u],low[v]). Aren't they part of the same component. Won't the final answer be the same regardless. An explanation will be highly appreciated. Thank you.
low[u]==dis[u] is head node then why low[2]==dis[2] but i t cannot be head node?? at 11:04
At 15:16, you did not explain why it is cross edge and not a tree edge.