Modernization Hub

Modernization and Improvement
Strongly Connected Components Kosaraju’s Algorithm Graph Algorithm

Strongly Connected Components Kosaraju’s Algorithm Graph Algorithm


Hello friends my name is Tushar and
today I’m going to talk about how to find strongly connected component using
Kosaraju’s Algorithm. So what is strongly connected component?
So here I have a directed graph and a strongly connected component in a
directed graph is a compliment such that all the vertices in that component is
reachable from every other vertex in that components. So here I have 4
different strongly connected components.1 of them is a ABC so A is reachable both
from B and C and C is reachable both from A and B and B is reachable both from A and C.
Similarly DEF is a strongly connected component, GHIJ is a strongly connected
component and then K is a strongly connected component. So what are possible
applications of strongly connected connected component. One of them could be
in Facebook for example Facebook is graphs of people and then Facebook
would be using this algorithm to find all the strongly connected people
with each other and then could be looking for common interests or
something like that in that component. So how do we find strongly connected
component. There are couple of algorithm to find it. One of them is
Kosaraju algorithm which we are going to discuss today. It’s a 2 pass algorithm
Basically it goes through this graph 2 times. So in the next section let’s see how
this algorithm works, why it works and then we’ll in the end look at the code
As I said it’s a 2-pass algorithm. So let’s see what we do in the 1st pass.
So we do a DFS on this graph and then we order the vertices of this graph by
finish times in decreasing order. So we need 2 data structures, a set to keep track
of all the vertices we have visited and a stack to order the vertices by
finish time. So we can start from any vertex. Let’s say we start from B. So
we, first thing we do is we put B in visited. Then we explore the
children of B. So B, let’s say go to C so C is not in visited so we go to C
put C in visited. Then explore the children
of C so there’s only one child A and A is not in visited so we put A in visited
and then explore children of A and that’s B but B is already in the visited. So we
don’t go to B. So at this point we have we’re done visiting all the children of A so,
which means that there is, A is done,A is finished. So A is the first vertex
to finish. So let’s put that in stack. Then go back in recursion and go to C and
C has no other children so C is done so we’re totally done visiting C. So
we push, we push C into the stack. Then we come to B and then B has
another child D so we go in the direction of D and D is not in visited so we’ll
put D in visited. Then D has another child E and E is not in visited so we’ll put E
in visited and then E has another child F and F is not in visited so we’ll
put F in visited and then F has child d but D is already visited so we go back
to F. F has no more children to be explored so we’ll put F into this stack and then we go
back to E and then E has no more children to be explored So we put E
into this stack and then we go back to D and then D has no more children to be
explored so we put D into the stack and from D we go back to B. So at this point B
has explored all its children. So we’ll put B into this stack. Then, then we pick another vertex
which has not been visited. So let’s say we picked I. So I is not visited so first
thing we do is we put I in visited. Then we explore children of I. So there’s only
one child of I, that’s J and J is not visited so we’ll put J in visited and then
we’ll explore children of J so let’s say K and K is not visited so we’ll
put K in visited and then K has no more children. So K is done. So we’ll put
K into stack and then we go back to J and J has another child G so we go to G,
put G in visited and then G has another child F but F is already visited so we’ll
do nothing. At this point J has another child H. So we’ll go in the director of
H, put H into stack and then H has a child I but I is already
visited so we’ll not go there so at this point H is done visiting
all its children so we’ll put H into stack. Then we’ll go back to G. G has done visiting
all its children so we’ll put G into stack Then we’ll go back to J and J has done
visiting all its children so we put J into stack and then finally we put I
into this stack. So this is the first pass of this algorithm and I have this
stack in which the vertices are ordered by finish time in decreasing
order basically the vertex which finished last for example I is at the top of the stack
and the vertex which finished first for example which in this example was A which is at the
bottom of the stack. So next let’s see how we do the second pass. So first thing I
did was I reversed my graph then in the second second pass I’m going to pop elements out
of this stack and do a DFS on this reversed graph. So let’s pop out I
and since I is not visited I put I in visited and this is my first strongly
connected component starting with I. So from I, I go to H so H is not in the visited
so we’ll put H in visited and then also add H as a part of this strongly
connected component and from H we go to G and G is not in visited so put it in
visited and add it as a part of strongly connected component and from
G, I go to J, J is not in visited so add there and add it here and from J we go to I but
I is already visited so J has no more children to be explored, G has no more children to be
explored I has no, H has no more children to be explored
and then I has no more children to be explored So basically we are done exploring all
the nodes from, vertices from I so basically this is our first component.
So at this point we’re going to go back into stack and pop out the next
element but this,this strongly connected component, the first strongly connected component is done. So then I pop out J but J is already part of
visited so I do nothing. Then I pop out G. G is already part of visited so I do nothing.
Then I pop out H, H is already part of visited so I do nothing. Then I pop out
K. K is not in visited so I add K here then I start the DFS from K. So this is
start of our 2nd component,strongly connected component. From K we can go to J but J is
already in visited so we come back to K and then K has no other child to
be explored in this graph so this this second stronly connected
component is just one vertex. So at this point we’ll go again into this stack and pop
out next element so that’s B so B is not in visited so I’m going to add it in the
visited and this is going to start my third component. So from B i can go to
A. So A is not in visited so I add here and then I add it here and then
from A I go to C. C is not in visited so I add it here and then I add it here
from C I can go back to B but B is already in visited so I go back to A. A
has no other children and then B has no other children so at this point we are done
exploring all the vertices vertices of this strongly connected
component. So then we’re going to start the next component. So we pop out D. D is
not in the visited so we add it here and we’ll start a new component here D and D has a
children F and F is not visited so we add F here and add F here
and then F has a child E and E is not in visited so we add E here and then we add E here
and then E has a child D but D is already in visited so we go back to E and
E has no other child and F has no other and D has no other child so this is
the 4th component and D has, D has another child B but B is already visited so
we’ll not go there So this is it. So D,so this is DFE is our
4th strongly connected component. Then I’m going to pop out E but E is already
visited then I’m going to pop F and F is already visiteded and then I’m going
to pop out C and C is already visited and then I’m going to pop A and A is already
in visited. So these are our 4 strongly connected components. IHGJ, K, BAC and then DFE. So let’s
analyze the time complexity and space complexity. So the, time complexity is
we did, in the the first pass we did the DFS so that will take O(E+V) time where E is number
of edges and V is the total number of vertices and then we reversed this graph and that
will take another (E+V) time probably depending on how the graph,how
you have represented your graph and then we did another pass on this,on
this graph, on the reversed graph and then we take another O(E+V) time. So the total time
complexity will be O(E+V). Space complexity is pretty
simple. The total number of elements in the stack
is total number of vertices and in the visited set is also total number of vertices.
So the space complexity is O(V). So in the next section let’s try to understand why
this algorithm works. CLRS book has a mathematical proof on why this algorithm works
but let’s see some intuition behind it. What I’m going to do is I’m going to
combine my vertices of a strongly connected component into one vertex and
create a new graph. So this ABC is one vertex and then DEF is one vertex
and then GHIJ is one vertex and then K is one vertex. Then
there’s an edge from this side of this strongly connected component to here
so we’ll create this edge. There’s an edge from here to here so we’ll create this
and then this. So what I’m saying is this graph is
guaranteed to be directed acyclic graph. Why? Because if there was a cycle here, for
example if there was this edge from here to here it means, for example there is an
edge from here to here. Then this combined
together would be 1 strongly connected component so we won’t have,we would not
have this edges as two different edge we won’t have this as 2 different
vertices but we would have this 1 combined vertex. The fact that we are
having this 2 different vertices it means that there is no cycle and it
means that this edge is not possible. So that shows why this is going to be a
directed acyclic graph. Now we did the ordering of vertices based on their
finish times. What that meant was that when all the children of, when all
children of a vertex are explored then put in a stack. So there’s a
guarantee that at least 1 vertex from this set is going to finish after this guy
because there’s an edge from here to here there’s a guarantee that there
will be at least 1 vertex here which will finish after all this guys are explorered. So let’s say that guy
was B. So in the, in the stack A and C went down then all this DEF goes on top of that
but at least 1 vertex from this set and let’s say that’s B will always fell on top
of this guy because there is a there’s a edge from this side to this
side. Similarly there’s a guarantee one vertex from here will finish
after all these guys are explored. Let’s say that guy was G so and then there’s
also guaranteed at least one vertex here will finish after K and let’s say
that guy was G. So then what we did was we reversed this graph. So when we reversed this graph this
will pretty much end up looking something
here will finish after K and let’s say
that guy was G. So then what we did was we reversed this graph. So when we reversed this graph this
will pretty much end up looking something like this. So by reversing this doesn’t
change because all the vertices are vertices are reachable from each other. They’re continue to be, they
will continue to be reachable from each other because it’s strongly connected component. Similarly
for these other strongly connected component. But this vertex this edge will have a different direction now
because we reverse this direction. So then what we did was we did a DFS based on
the finish time so what we, what guarantee we had was that B and G will
be picked before this, any of the vertex here or any of this vertex here is
picked. So when B got picked first we explored everything here so ABC got
explored and then we and then we finished and B could not explore anything here
because this, this, there’s an edge from this side to this side and then when G
got selected next G explored everything here so GHIJ and then by the time
K got selected or any of the edges any of the vertices in this group got
selected these 2 guys, all the vertices in this were guaranteed to be
explorer which is why when DEF got selected DEF could not explore,explore
any further because all these guys were already explored by either B or G and
similarly when K got selected K could not explore further because these guys were
guaranteed to be explored before K got selected. So that is how we ended up
having four different strongly connected components. Hopefully this gives you some intuition
why this algorithm works. Anyways as I said CLRS book has the full explanation
of the proof. So in the next section let’s quickly look at code for this algorithm. So we’re going
find strongly connected components. So my main function is scc which takes a graph and
then it returns a list which is a list of set where each set represents a
strongly connected component consisting of vertices. So first I initialize the
stack and then I initialize a set. So what I’m going to do is in the first pass is go through all the vertices, do a
DFS and order the vertices by the finish time in decreasing order. So let’s
say we start from vertex 2. So visited doesn’t contains 2 so we go into this
DFSUtil with 2 as the vertex so the DFSUtil is a very simple function. All it
does, it does a DFS and puts the vertex in a stack when it’s done exploring all
its neighbors. So we go, we start with 2 we add 2 to visited. Then we explore
neighbors of 2 so we get 3.3 is not visited so we call DFSUtil with 3,add 3 to
visited and then explore neighbours of 3 so let’s say we get 1.1 is not
in visited so we go into DFSUtil with 1 so we add one to visited and
then explore neighbors of 1 so we get 2.2 is in visited so we continue and then
there is no more neighbors of 1 to be explored so we add 1 to the stack. Then
we go back in recursion,go back to 3,explore another neighbour of 3
that’s 5.5 is not in visited so we add 5 to visited then explore neighbour of 5
which is 6 so 6 is not in visited so we add 6 to visited and then explore neighnour of
6 which is 4.4 is not in visited so we add 4 to visited and then explore number 4.4,
his neighbor is 5 which is in visited so we continue and so we’re done
exploring all the neighbors of 4. So at this time we add 4 to the stack and we
roll back in recursion where 6 was the vertex and 6 has no more neighbours to
be explored so we add 6 to the stack and then we roll back in recursion and
then add 5 to the stack and then come back to 3 and 3 has no more neighbours to
be explored so we add 3 to stack and then come back to 2 and 2 has no more neighbours to
be explored so we add 2 to the stack. Then we go back to the top our main function and then we explore
another vertex which has not yet been added to the visited so that vertex is
7 so we again call DFSUtil with 7 and add 7 to visited. Then
explore neighbours of 7 that’s 6.6 already is in visited so we don’t
go into recursion with 6 and then at this point 7 doesn’t have any more
neighbours to be explored so we add 7 to the stack. and then we go back to the top of, to
the main function. So at this point we have populated this stack and with the
with the vertices in a finished time in decreasing order. So next let’s reverse
the graph and do the second pass.So I reversed this graph and then I’m going to
do a DFS on this graph based of the vertices coming out of this stack. So
we cleared our visited set and then I create my result list where I’m going to
store all the strongly connected components. So while stack is not empty I poll out the first element, first vertex from
this stack. So 7 comes out of the stack and then we do a DFS on 7 so visited
doesn’t contain 7 so we create a new set for storing this strongly connected
component and go into this recursion DFSUtil for reversed graph. So in DFSUtil
for reversed graph first thing I do is I add 7 to visited then I add 7 to a set and
then I explore neighbours of 7.7 doesn’t have any neighbour in this reversed graph
so we do nothing and we go back to our main function and then in here we add this
set to our results list. So this is the first set in my list. Then I go back here
while stack is still not empty so I pop the next element out of the
stack and that’s 2 and visited doesn’t contain 2 so we create a new
set and then again call this DFSUtil
for reversed graph and in here first thing I do is I add 2 to visited and then
I had 2 into this new set and then I explore neighbors of 2 so first
neighbor I get is 1 so 1 is not in visited so we called DFSUtilForReversedGraph for
1. So first thing we do is we add 1 to visited and then add 1 to the same
set as we added 2 and then explore neighbours of 1 so that’s 3. 3 is
again not in visited so we again call this DFSUtilForReversedGraph add 3 to
visited and add 3 to this set and then 3 has a neighnour 2 which is already visited so
we roll back in recursion, go back to 1.1 doesn’t have anymore neighbour so
we go back to 2 and then 2 has no more neighbours so we’ll go back to the
top of this main function. In here we add this (2,1,3) set to our result and then we
pop out the next element from this stack so that’s 3.3 is already visited so we do
nothing about 3.Then we pop out the next element from the stack and that’s 5
So 5 is not in visited so we create a new set and then we again go into the
recursion with 5 so we come here,we add 5 to visited then we add 5 to
this set and then explore neighbours of 5. So the first neighbour of 5 is 3 but
3 is already visited so we do nothing about it so then the next
neighbor of 5 is 4 so 4 is not visited so we go into the recursion for 4.So
we add 4 to visited and add 4 here and then 4 has a neighbor 6,so and
6 is not visited so we put 6 in visited and add 6 here and then 6
has neighbor 5 which is already visited so we do nothing and then 6 has another
neighbour 7 which is also visited so we do nothing and then
we’re done exploring all neighbours of 6 so we go back to 4 and then we’re
done exploring all neighbours of 4 so we go back to 5 and then we’re done
exploring all neighbours of 5 so we go back to the top of this,this main
function. In here we add this set to the result and then we explore,we explore
the next,next element from the stack so that’s 6.6 is already visited so we do
nothing and then we poll the next element from this stack so that’s 4, it’s
already visited and then 1 is also already visited. So this is our this is our strongly connected
components 7,213 and 546. Again the run time complexity is O(E+V)
and the space complexity is O(V). So that’s all I have to talk about strongly
connected components. Please like this video,share this video,comment on this
video,check out my facebook page,check out my github link and the link,the link
to the code is in the description section of the video. Thanks again for
watching this video.

100 comments on “Strongly Connected Components Kosaraju’s Algorithm Graph Algorithm

  1. Awesome explanation..
    here is the C++ Implementation
    http://www.binarycoder.org/data-structure/strongly-connected-components-graph/

  2. great video, could you also make a video about finding clique in a graph, I couldn't find any good video in youtube yet and your videos are very easy to understand. thanks!

  3. This is beautifully explained. I was struggling to find an intuitive explanation for why this algorithm works until I found this video. Thank you!

  4. can we say that the first pass is like topological sort implementation except the fact that topological sort cannot be applied on the cyclic graphs?

  5. +Tushar Roy : How about directions of edges of those strongly connected components? How do I represent that as a graph?

  6. Very nice explanation of the intuition.

    "By intuition that we discover and by logic that we prove" – Henri Poincaré

  7. Children is already plural. You don't need to say childrens. Also, this video was dank af thanks bro, gonna ace my exam tomorrow. Let's smoke some hash soon my dude

  8. I was stuck at this topic for an hour or so. Thank you for explaining with an example. Not only it was so easy to understand, no i believe that i can teach it somebody else too.

  9. wonderful explanation especially the intuition part. can you make a video on <a href = "https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm" > algorithm </a>

  10. How do you ensure you've covered the entire graph in the first pass? We will have to do a set different b/w seen and the total graph and restart if it is non-zero – right?

  11. Dude, you are awesome,
    You finished all my doubts that came into my mind sequentially while watching this video.
    Hats off /

  12. Great job. Whenever I search any algo on YouTube I search for your videos first. You explain everything simply and quickly.

  13. Turshar…Please remove the background of the subtitles… its disturbing to see what you are writing on bottom of the board…

  14. I have watched all your videos about the algorithm, that's awesome!! really helped with my review and restudy!!! thank you so much 🙂

  15. I want to make sure I understand you correctly @13:10, originally you considered the SCCs
    B G
    [ABC] –> [DEF] <– [GHIJ] —> [K]

    "There is a guarantee that at least one vertex (say B) in [ABC] which will finish after all vertices in [DEF] have been explored"
    @13:34 you say
    "all this DEF goes on top of that but at least one vertex from [ABC] (say B) will always be on top of [DEF]"
    I believe you meant to say "below of [DEF]", since if B is guaranteed to finish after all vertices in [DEF], B must be below vertices in [DEF]. Please verify.

  16. is cycle considered strongly connected then? what is the difference between a cycle and a strongly connected graph? And.. is that graph considered acyclic or cyclic since there are multiple cycles in it. I know you said the graph is acyclic but how come? what about the three cycles in it? (ABC & DEF & GHIJ ). Please help answer my questions as I'm super curious to find out. 🙂

  17. banjau tera chela mujhe boht kuch sikhaana hai teri DSAlgo ki knowledge dekhke meri bndi bole mujhe isshi se DSAlgo sikhne jaana hai.

Leave a Reply

Your email address will not be published. Required fields are marked *