Tarjan's Strongly Connected Component (SCC) Algorithm (UPDATED) | Graph Theory
Vložit
- čas přidán 2. 06. 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!
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!!.
By far the most succinct explanation of Tarjan's SCC algorithm, thanks!
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. :)
Love your way of explaining algorithm concepts
Your channel deserves much more views ! Subscribed !
This is one of the best video on Tarjan's Algorithm . Thanks alot !!! 😄
Great explanation. Thanks William
Hey William! Great graph collection there, can you put videos on articulation points and bridges?
Amazing explanation! Thanks!
That was a great explanation! Thanks!
Great video, thank you for the explanations
great visuals! beautiful algorithm
thank you so much, watched this just in time!
Very nice explanation. Thank you
Very nice video, which editing software did you use to make the video William ?
It took some time to understand, your video helped
an excellent explanation, thanks a lot.
I just love your content! 🙌
Very interesting video to learn from, thanks
Hey William did u take down your articulation point video? I couldn't find it on your playlist
Thank you very much, that was amazing!
Beautifully Explained :)
why did you remove your bridges and articulation points video ? you kept the older version of this. awesome series though !
Super Good Explanation!
Thts a indepth Easy Explanation of a Complex Algorithm ,
Very comprehensive!
Best video on CZcams for Tarjan's Algo
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?
thanks for a super clear example
Incredibly helpful.
Clear and awesome!
amazing videos man!
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.
Just to drop this! Great
very beneficial , Thank You
Keep on making helping a lot, you are bringing change!!! thanks man
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
Geat explanation. Thanks.
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?
Awesome! Thank you!
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.
Thanks for this video :)
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
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.
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?
Can you make a video on the theme of the Feedback arc set? Your videos are very good!
this really helps. thx
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 :)
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.
my teacher took 1.5 h to explain this concept and explained it in 9 min ( after playing it at 2x speed😉). Thank you
Good explanation. How do you extrapolate this to finding critical connections in a graph ?
See his Bridges and Articulation points video: czcams.com/video/aZXi1unBdJA/video.html
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
Loved it
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
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
Thank you Sir
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.
can you use tarjan to find articulation points?
Cool as ever.
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!
Thanks!
Anyone knows of any problems on LC that relies on finding SCCs?
1319 is connected components, but can't find a question for SCC.
Can we have Johnson's elementary cycles algorithm?
This was a beautifully written explanation. Thank you!
Awesome dedication to helping the viewer understand rather than "look what a l33t h4x0r i am"
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.
Do I understand correctly that you explained to us that the effect of algorithm finding value of index is highly dependent on... indexing?
Why we need stack data structure ? bool onStack[n] should just help ??? Please help me understand...
Thanks you~!
I don't understand what will be the run time and space complexity?
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
Good Idea, to separate the Lowlink-calculation from the Rest!
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).
Wouldn't 16:19 be cleaner with a while loop?
what do you mean by lowest node id?
super!
Awesome
Thanks
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".
whats if node 0 was not visited when we reached 5?
did not Tarjan lived in the jungle.
Jen is disappointed reading this
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 czcams.com/video/aZXi1unBdJA/video.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 czcams.com/video/aZXi1unBdJA/video.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.
ORZ🔥🔥🔥🔥🔥
Hey, are you active on some media. Would love to talk!
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
He sounds like ParashockX
*scratches head* What is this sorcery?
why is node 4 at this location czcams.com/video/wUgWX0nc4NY/video.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
Hey. What would happen if i had a graph with a node which points only at itself? Would that Node be considered a cycle?
And does this Algorithm return the amount of cycles in the graph or just tells us that the graph is cyclic? Will the Algorithm always return the same cycles and the same amount of cycles or does it depend on the starting point?
This algorithm per se doesn't talk about cycles. It computes the connected components in a graph which are different from cycles.
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_ ?
If you are still hungry to know more about Tarjan's Algorithm, and especially, if you are curious to know how Tarjan's Algorithm is derived and why this algorithm actually works, visit the below links:
Full explanation: www.thealgorists.com/Algo/GraphTheory/Tarjan/ArticulationPoint
Finding Bridges: www.thealgorists.com/Algo/GraphTheory/Tarjan/Bridges
Finding SCCs: www.thealgorists.com/Algo/GraphTheory/Tarjan/SCC
i have c++ backgrond, and trying to understand this code, but this for loop is not clear to me,
for(node = stack.pop();;node=stack.pop()):
can someone help to translate in c++ loop please
As some people pointed out, the algorithm is flawed, as you present it. When you are presenting on the 8-noded graph... if there was an edge from 5 to 3, your algorithm breaks.
I just reached the enlightenment... your explanation through low-links actually confused me greatly. In the algorithm, you actually do NOT ensure that the lowlinks match, but you keep track of the lowlinks only to know when to terminate and start popping from the stack. Maybe it is just me, but I thought someone might get confused the same way.