## 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.

very well explained !!!!!

Here in your example G and I are not connected. then how g,h,i and j are strongly connected?

Great

I am sorry, couldn't quite catch the name of the book … what is the book's name ??

what do you mean by "decreasing order of finishing time", when inserting nodes in the stack during the first pass?

At some point, the learning stops and the pain begins.

Awesome explanation..

here is the C++ Implementation

http://www.binarycoder.org/data-structure/strongly-connected-components-graph/

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!

Nice Video, very simple easily instruction of a complex problem

clear illustration. all your videos are so awesome. thank you for your effort

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

Keep up the good work!

awesome explanation!! Thank you so much

superb explanation!!!

sir please make a video for biconnected components also….this was a nice explanation!!

your way is hard to tracking back……..but it's clear thanks

Fantastic explanation. Congratulations!

Very well explained. Thanks

thanks a lot. ?

Clear and worth watching (y)

great explanation sir.thanks 🙂

Thank you!

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?

Great explanation, thanks buddy!

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

You are the best man

Very nice explanation of the intuition.

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

Thanks Sir, For such a great explanation.

great work

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

good tutorial sir 🙂

please do something for subtitles because they cover screen.

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.

Awesome explanation !!

your accent is not good man.make it clear

He makes it look so simple!

Hats-off to him 🙂

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>

what do you mean by Strongly Connected Component? ..aapke papa samjhayenge

excellent !!!!!!!!!!!!!!!!!!!!!!!!!!!!! amazing to have you in youtube!!!!

Very good explaination, thank you Roy

very clear and smart explanation

nice explanation especially why the algorithm works

awesome

great explanation

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?

Thank you so much!

Awesome explanation Tushar! Thank you 🙂

Great explanation! Thank you so much!!

Thanks you very much

Dude, you are awesome,

You finished all my doubts that came into my mind sequentially while watching this video.

Hats off

/Nice Explanation

Thank you very much, this was really helpful! Good job! 😀

just what I needed – thanks bud!

sir can you please upload a video on strongly connected components using tarzan's algorithm!

thats cool

the stack essentially contains the topological ordering of the graph right?

People with upper arm hair turn out to be rapists.. JK…good tutorial

Thank you.

legend

Perfect

Iam sorry sir. I failed to understand ur explanation in first move. Its little bit confusing.

What an amazing explanation. Thank you very much!

useful but please use normal english as your 'staaack" hits in ear

aint no better explanation than this

Wonderfully explained. A lot to learn from you. Keep up the good works.

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

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

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

Great work! Thanks for putting up this awesome video! It really helped my studies.

11:20 intuition on why the algorithm works

nice explained sir….

Thank you!

adbhut avishwaniya .. itna accha explanation .. bahut kam hi dekhne milta hai …

great tushar bhai ! !

Amazing intuition provided!

fucking brilliant man!

how to learn to code graphs easily? i feel they are above my limitations : (

absolutely perfect explanation!

at 9:09 from vertice D we should check B first, then F if we traverse lexicographically!

Sir how to find cn chain by an edge

thanks

surprisingly a good explanation.thanks!

It will be better to remove subtitle

Because it covers some part written on board

Can you make the tutorial for tarjan's algorithm?

Good job! Thank ya!

But why this solution works?

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.

Wonderful!!! you helped me a lot, thanks!!!

The first pass is a topological sort right?

Thanks a lot for great explanation.

Thank you 😉

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. 🙂

thanks man, your class helped me a lot

thank you what a high quality works

from 14:00 to 16:00 its the fruit of logical reasonng

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

Kosaraju was an Indian.

Hit like if you didn't know this before.

Proud Indian

very nice

just speak naturally !!

Perfect explanation step by step. Good job ?

Very well explained, bro. Did a nice job.