Tarjan's Strongly Connected Component (SCC) Algorithm (UPDATED) | Graph Theory
Вставка
- Опубліковано 15 лип 2024
- Tarjan's Strongly Connected Component (SCC) algorithm explanation video.
Source code video:
• Tarjans Strongly Conne...
Algorithms repository:
github.com/williamfiset/algor...
Slides:
github.com/williamfiset/Algor...
Website:
www.williamfiset.com
===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
This series of algorithm explanation is really awesome and helpful!
By far the most succinct explanation of Tarjan's SCC algorithm, thanks!
Thank you! I watched like 5 other videos that all missed calling "only set the low if the node was on the stack" and it confused the heck out of me. Thanks again.
Images speak more than the words. How Beautifully you explain such a compelling algo. Thank you!!.
I'm not a native English speaker, your English is slow and clear, very nice video :), learn algorithm and your English pronunciation
I just love the way you explain everything and make it easy to understand. Kudos to that!
incredibly well explained, you're trully talented at this, keep up the good work!
Thank you so much for this, all your videos make these concepts so much easier and clearer to understand!
Finally, a well explained video of Tarjan's algorithm.
This is pretty much exactly what I needed.
Thanks for the well made explanation. :)
did not Tarjan lived in the jungle.
Jen is disappointed reading this
Love your way of explaining algorithm concepts
This is one of the best video on Tarjan's Algorithm . Thanks alot !!! 😄
Your channel deserves much more views ! Subscribed !
Great explanation. Thanks William
great visuals! beautiful algorithm
This is a great explanation!
That was a great explanation! Thanks!
Amazing explanation! Thanks!
Just to drop this! Great
Great video, thank you for the explanations
Clear and awesome!
thank you so much, watched this just in time!
I just love your content! 🙌
Super Good Explanation!
an excellent explanation, thanks a lot.
Very nice explanation. Thank you
It took some time to understand, your video helped
Beautifully Explained :)
Incredibly helpful.
Best video on UA-cam for Tarjan's Algo
Thank you very much, that was amazing!
Very interesting video to learn from, thanks
Hey William! Great graph collection there, can you put videos on articulation points and bridges?
thanks for a super clear example
Very comprehensive!
Geat explanation. Thanks.
Awesome! Thank you!
Thts a indepth Easy Explanation of a Complex Algorithm ,
amazing videos man!
very beneficial , Thank You
1. To update node u's low-link value to node v's low-link value there has to be a path of edges from u to v. U -> V
2. Node v must be on the stack. V -> U
So, 2nd point actually mean there has to be a path also from node v to node u.
And we can update u''s low-link value from v's low-link value.
Thanks for this video :)
Keep on making helping a lot, you are bringing change!!! thanks man
Very nice video, which editing software did you use to make the video William ?
Thank you Sir
So , basically a cycle is strongly connected component and tarjan saw this opportunity to make one more algorithm out of this. It is just glorious form of cycle detection in a directed graph. where we are keeping track of all the cycle
Loved it
this really helps. thx
Thanks a lot... This is a wonderful video.
Possible Correction in the code:
if(onStack[to]): low[at] = min(lo[at], lo[to])
The above statement would never run as after recovering from any dfs call, once the SCC gets identified, you've already popped off the entire stack.
Safely enough, we've already assigned the lo-values to all nodes of connected componenets just when we identified an SCC.
Tell me if I'm wrong btw.
This is old but you are wrong.
If a node is a neighbour to another node we already visited, it may happen that we haven't searched all the neighbours of that node, and thus haven't poped it from the stack. which means that they are in the same SCC so we update accordingly the low link.
Many thanks for the very clear video!
What about a video on a closely-connected (yes😏) algorithm to find all cycles in a directed graph, namely Johnson's algorithm?
You are the goat brother! 🐐
Thanks!
why did you remove your bridges and articulation points video ? you kept the older version of this. awesome series though !
Hey William did u take down your articulation point video? I couldn't find it on your playlist
Cool as ever.
Thanks you~!
Can you make a video on the theme of the Feedback arc set? Your videos are very good!
can this algorithm be detected nest SCC? for example at 1:10 the red circle (0) -> above the purple circle
-> next purple circle -> -> below the purple circle --> red circle (1). Now we have 2 SCCs, one is 3 purple circle and bigger SCCs is 3 purple + red.
Hey, I wanted to know why we update the value of low a second time when we pop elements off the stack? It feels redundant to me
I saw an another video by you which explains how to find bridges and articulation points. Can you tell me why tarjan's algorithm is needed and in what cases your previous algorithm for finding bridges and articulation points does not work?
Thanks
super!
my teacher took 1.5 h to explain this concept and explained it in 9 min ( after playing it at 2x speed😉). Thank you
Awesome
Hi William - this video was helpful, but can you include links to cycle detection in directed and undirected graphs? Tarjan's was much more intuitive after first understanding cycle detection in directed graphs via DFS. Also can you review the difference between weakly connected vs strongly connected in direct graphs - I think that would help.
Cycle detection is simply when, while doing dfs you find a node you've already visited as a neighbor of the current node you're visiting.
Thank you so much for the content. Would you consider removing the old content? I was watching it, and noticed what might be the issue with it, but for a while I thought I missed something until I read the comment. Also, is there any relation between two different SCCs?
Why we need stack data structure ? bool onStack[n] should just help ??? Please help me understand...
This was an amazing explanation! I have one question though: in dfs function, @16:51, is `low[node] = ids[at]` line inside the stack-pop for-loop actually necessary? It seems to me that the low[node] should be properly set everytime a node is called back.
even i have same question do u get the info regarding this ,this hould be written or not?
@@ANUJ-we3su Yes it is, a good example is a directed square (1 SCC) with a triangle (starting from top left node) :
o--o--o
| | /
o--o
@@clementdumas6371 I still didn't get it, can you please elaborate ? I still think we don't need to set low[node] = ids[at], as they will be set corrected during dfs itself.
A bit late to this party, but to answer your question - No, 'low[node] = ids[at]' is not needed because by the time you to the stack.pop loop, the lowlink values of the SCC members have already been set. Of course you can just debug a quick example and see for yourself :)
can you use tarjan to find articulation points?
Anyone knows of any problems on LC that relies on finding SCCs?
1319 is connected components, but can't find a question for SCC.
for the code, in the visiting neighbor step, you shouldn't be able to do onStack on the previous node. This will cause the entire thing to fail
fix is to skip the iteration if the neighbor node is the previous node.
Hey, thanks a lot for your videos! Is it necessary to assign low[node] = ids[at] while popping the stack (at the end of dfs function)?
Good question, i also didn't get it
Same question!
Yes, it's necessary because the low array will be the output of the algorithm. The low array is used as a kind of SCC identifier. If the condition "ids[at] == low[at]" is true, the current node is the start of a new SCC, which contains exactly the nodes that are currently on the stack (above and including the current node). This is why we assign each node on the stack the same low value. After the algorithm is finished, all nodes with the same low value are part of the same SCC.
Edit: He also could have added "create a component" as the first line inside the "if" and replaced the "low[node] = ids[at]" with "add node to that component". This is essentially what's going on.
@@waldtrautwald8499 But the nodes that are part of that SCC should already have the same low value from the "if(onstack(to)): low[at] = min(low[at], low[to])" step or am I missing something?
@@waldtrautwald8499 Nevermind I found an example that shows the nodes of an SCC don't need to have the same low values before the "ids[at] == low[at]" step
Can we have Johnson's elementary cycles algorithm?
I don't understand what will be the run time and space complexity?
hi, why does the algo ensure low[node] after popping from stack? does this line low[at] = id++ not guarantee that?
Look here for full explanation: www.thealgorists.com/Algo/GraphTheory/Tarjan/SCC
Wouldn't 16:19 be cleaner with a while loop?
Good explanation. How do you extrapolate this to finding critical connections in a graph ?
See his Bridges and Articulation points video: ua-cam.com/video/aZXi1unBdJA/v-deo.html
Low-link , is not smalest node id reachable from node i , its smalest node that's can reach just using one back-edge in DFS tree
Do I understand correctly that you explained to us that the effect of algorithm finding value of index is highly dependent on... indexing?
Why did we use DFS here and not BFS?
(I kinda know we have to reach all possible paths from a node still looking for some structured reason)
Thanks in advance!
what do you mean by lowest node id?
whats if node 0 was not visited when we reached 5?
Good Idea, to separate the Lowlink-calculation from the Rest!
This was a beautifully written explanation. Thank you!
Awesome dedication to helping the viewer understand rather than "look what a l33t h4x0r i am"
at 16:45 we are setting low[node] to ids[at]
would it not have already happened above when low[at] = min(low[at], low[to])
this seems redundant. what am I missing??
got the case
0 -> [1], 1 -> [0, 2], 2 -> [1]
here we have low link value to start will be
[0, 1, 2]
we start traverse from 0 and dfs to 1.
at one we may do either of two ways
1. traverse to 0 then 1
2. traverse to 1 then 0
if it is 1st case then all is good 2 will also get a low link value of 0
in 2nd case 2 is traverse and marked low link value of 1 as 1 has low link value of 1 at that point. 1 will then traverse 0 later and get a low link value of 0 but it will not be propagated to 2 at that point.
hence we will need to re assign low link values to stack once we come back to original node which we started with if it’s low link value is itself.
to ensure we propagate low value correctly we would have to choose neighbour we already visited first which will increase the time complexity
awesome explanation.
but in the pseudo code, when i replace low[at] value with min(low[at], low[to]) why do i again need to carry out
low[node] = ids[at] while removing from the stack ?
also, i found a similar code somewhere else with a minor difference which is min(low[at], ids[to]) instead of min(low[at], low[to]).
please clarify the doubts...thanks in adv
Yeah, it seems to work without the low[node] = ids[at], at least when I ran it with the example from the video.
@@MatthewLuigamma032 It doesn't work for all examples tho
@@MatthewLuigamma032 One example to show this:
A->B
B->D
D->E->C
E->A
C->B
If you start dfs at the A node the C node should have a low value of 1 while the others have a low value of 0 before the "low[node] = ids[at]" step
ORZ🔥🔥🔥🔥🔥
Thank you for your clear explanation and awesome animation. I have one question though: I came across the pseudocode of this algorithm on Wikipedia: en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#The_algorithm_in_pseudocode
It seems that they update the low link value differently:
if ( ids[to] == VISITED)
{
dfs(...);
low[at] = min(low[at], low[to]);
}
else if (onStack[to])
{
low[at] = min(low[at], ids[to]);
}
Wikipedia even said that when to is onStack, updating low[at] as min of low[at] and ids[to] is deliberate (ids[to], not low[to]).
I'm just wondering if this is needed or your code has covered this case?
Thank you.
Same question here. Would appreciate it greatly if you could explain this part. Seems to relate to the back edge vs the tree edge. But I'm not sure what's the difference in the code. Many thanks!
Even I'm confused about this part. Any explanations will be helpful. Thanks
@@thealgorists60 I'm sorry if my comment is late, but although it's necessary to distinct between low[at] = min(low[at], ids[to]); and low[at] = min(low[at], low[to]); in cases like bridges and articulation points, does it actually matter in this specific case of finding SCCs?
Like, I've tried both method, and both return AC (accepted) on the checker server, for the SCC problem (not the bridges or articulation points, of course).
Beautiful explanation. One question however, when there is no SSC in the graph (like a simple one - directional chain, ie. A -> B -> C -> D) , then it can clearly be seen that sscCount will not be 0. Isn't that misleading? Or, what does that tell us?
Wouldn’t there be 4 SSC’s in such a graph (the length of the chain)?
@@constantijndekker8343 No, because you cannot get from B to A. Looks like you can only get from A to B. To be SCC you need to be able to get to every single node from every node in the SCC so like if AB that would be SCC.
Todd Chaney Hello Todd, what I meant was that {A}, {B}, {C} and {D} are distinct strongly connected components (so there are 4). I agree that A and B do not belong in the same component, because, as you write, you cannot get from B to A in any way.
Is the low[nodes] = ids[at] necessary?
I have the same doubt
@@ITwithIT Yes, bro it is definitely necessary, once refer to this example graph, and perform a dry run, You'll get to know. Actually, you'll have only 1 SCC in this example.
media.geeksforgeeks.org/wp-content/cdn-uploads/20190702123438/TarjansAlgorithms.png
Yes, it is definitely necessary, take a look at this example graph and perform a dry run.
media.geeksforgeeks.org/wp-content/cdn-uploads/20190702123438/TarjansAlgorithms.png
May someone explain it in more detail, please? I've watched the video and read the geeksforgeeks.com article and I still don't understand the logic behind it. Everyone just says "do it that way".
Also, it is not so clear from the video why low[node] = ids[at]. William says that we assign for each node of the SCC the same id of the current (root of SCC) node. But we may know that it is the SCC only if we see that one of the next nodes of the current node is the root of the SCC node (we have visited it earlier).
Also, this step is not covered when William tells us about the thought process in the slides. When he reaches the root of the SCC he has already updated SCC values and says "All we need to do is remove the SCC values from the stack".
Hey, are you active on some media. Would love to talk!
In a cycle of a graph only the end and start vertex is repeated. If you have, for instance, a graph containing the cycles 1 -> 2 -> 3 -> 1 and 2 -> 4 -> 2, then 1,2,3,4 form a SCC but *not* a cycle. So the thinking of self-contained cycles is a bit misleading/confusing here. Your example, in the beginning, is a special case where such SCCs do not appear.
I think there is some issue with the implementation of the algorithm presented here.
I tried to dry-run this algorithm on graph shown at timestamp 07:16 in ua-cam.com/video/aZXi1unBdJA/v-deo.html
Draw above graph on a paper and follow below steps, (Delete/ignore node 3 and node 4 from graph)
If you start dfs from node 0, it may run like this,
0 -> 1 -> 2
When running dfs at node 2, it may look at node 0 first(which is already visited) and, we will update node 2's low[2] to 0.
Why, because node 0 is in stack and, even if the node we are looking at is already visited, we are still updating low[at] to min(low[at], low[to]) and here, low[to] is low[0] which is 0.
Remember that we have initialized low[2] to 0.
Let us continue the dfs for node 2,
0 -> 1 -> 2 -> 5 -> 6 -> 7 -> 8
At node 8, if dfs looks at node 2(already visited), we will still initialize low[8] to min(low[8], low[2]). Here low[2] is 0 and is minimum of the two so, low[8] is initialized to 0.
Looking to node 5(already visited) will not change anything.
Now, we have initialized low[8] = 0 (Doesn't this look wrong?)
If dfs backtracks(node 8 doesn't have any more unvisited neighbors) like,
0 -> 1 -> 2 -> 5 -> 6 -> 7 -> 8 ---Backtrack starts---> 8 -> 7-> 6 -> 5 -> 2 -> 1 -> 0
During backtracking, low[8], low[7], low[6], low[5], low[2], low[1], all are initialized to 0.
This gives the entire graph as SCC.
Isn't it incorrect or am I missing something here ?
Edit :
After checking wiki, I'm pretty sure
if(ids[to] == UNVISITED) :
dfs(to)
if(onStack[to]):
low[at] = min(low[at], low[to])
is incorrect.
It should be modified to,
if(ids[to] == UNVISITED) :
dfs(to)
low[at] = min(low[at], low[to])
if(onStack[to]):
low[at] = min(low[at], ids[to])
The example you took is acyclic, which is the reason it returns a single SCC. Add few cycles in your graph and you will notice.
This algorithm searches for cycles and its neighbours if you look at it closely.
@@indiegypsy How is the graph acyclic ? I can see atleast two cycles (0,1,2) and (5,6,7,8).
Also, I'm talking about the graph at 07:16 in ua-cam.com/video/aZXi1unBdJA/v-deo.html
@@shubhamb4932 Sorry, I did not check the video initially...
Now I understood your question clearly. What you are saying makes sense. Even I checked for the correctness of the logic at other sources and what you have mentioned seems true to me too.
In fact, there is a pinned comment in the video you mentioned which also discusses the same thing.
@@indiegypsy Sorry for answering late, but modifying it to low[at] = min(low[at], ids[to]) does have some effect in a range of graph does it? Because I tried the min(low[at], low[to]) and got AC for both cases. It seems like unless it goes to very specific cases like this, whichever doesn't matter.
Is low[node] = ids[at] necessary?
Yes:
Consider this graph with 4 nodes [1,2,3,4] and edges 1->2, 2->3, 3->2, 3->4, 4->1
1 -> 2 -> 3 -> 2 (cycle 3 -> 2 -> 3)
3 -> 4 -> 1 (cycle 3 -> 4 -> 1-> 2 -> 3
The whole thing is one SCC.
if the dfs goes from 1 -> 2 -> 3 -> 2 (backtrack and assign low[3] = 2, low[2] = 2)
and then backtrack to 3 -> 4 -> 1 (backtrack and assign low[4] = 1, low[3] = 1, low[1] = 1
We see low[2] is left forgotten to 2 if we don't add the low[node] = ids[at] line.
This will identify SCC1 = [1,3,4] and SCC2 = [2] which would be wrong.
wouldn't back tracking happens from 1->4>3->2->1, in the last final backtracking. thus taking care of 2.
You're wrong. The order of the traversal would be
1 -> 2 -> 3 -> 2 (backtrack to 3 and assign low[3] = 2)
Then dfs from 3:
3 -> 4 -> 1 (backtrack and assign low[4] = 1, low[3] = 1)
Then backtrack to 2, assign low[2] = 1, then backtrack to 1, assign low[1] = 1
The wikipedia for tarjan's algorithm doesn't use "low[node] = ids[at]" either.
Yeah. This line really confuses me, and I can't think of a graph where it's necessary to include this line of code. @@kacy6014
*scratches head* What is this sorcery?
why is node 4 at this location ua-cam.com/video/wUgWX0nc4NY/v-deo.html not having the low-link value of 0 and why is it a 4? I am still finding this "low-link" concept hard to understand
He sounds like ParashockX
Isn't low link value of a node _v_ the smallest "id" of a node that is reachable from _v_ via a path of tree edges followed by _at_ _most_ _one_ _non_ _tree_ _edge_ ?
dude what happened to your voice...