Finding the strongest connected components using Kosaraju's theorem

Kosaraju's Theorem

When we know what the strongest connected components are, we must know or devise an algorithm to find them. The theorem that is commonly used is Kosaraju's theorem.

Let us dive deep into the Kosaraju's theorem.

First lets list out the steps involved in finding the Kosaraju's theorem.

Then we will devise an algorithm and finally go for the test case or example.

STEP 1:

The first step involves, performing DFS of the graph starting from any vertex and storing the vertices visited in a data structure D indicating as visited. 

STEP 2:

Now when there are no more directions to go, retrace back to the previous edge and push the elements in a stack S.

STEP 3:

Now when this step is over, reverse each direction of the graph.

STEP 4:

Now pop the first element and perform DFS. Wherever the DFS will stop, till that is our one strongly connected component.

Also at the same time store, the edges visited in D.

STEP 5:

At last, all the sequence are found

Let us now dive deep into the algorithm

int kosaraju(int v,struct gr *G)

{

       int c=0;

      for(i=0;i<v;i++)

       {

            if(i not in V)

            {

                  V[max]=i;

                   c++;

                  DFS(i,v-1,G);

           }

      }

      G=Reverse(G);

      for(i=0;i<v;i++)

         V[i]=-1;

      for(i=0;i<v;i++)

      {

             

            if(i is not in V and j=S.pop())

             {

                   V[max]=i;

                   c++;

                  DFS(j,v-1,G)

             }

      }

      print("Number of strongly connected components:",c);

}

void DFS(int s,int v,int *G)

{

            for(i=s;i<v;i++)

            {

                   printf("%d-",G->value);
                   S.push(G->value);

                   G->value=0;

                   if(G->next->value!=NULL and G->next->value=-1)

                                          DFS(s+1,v.G->next);

              }

}

Now let us move to our example.
We take the following graph

Now the graph needs certain naming. So let's take name them like below

Now, this graph is perfect. We take a stack
S:
This shows that stack is empty







we perform our 1st DFS move taking '1' as our selected vertex.
Thus, after our first vertex movement, our graph becomes

Stack S:
This shows S is still empty








V:1

After 1st DFS visited data structure has 1 as visited
After this, we move to our next vertex as 0

Stack S:
S is still empty








V: 10
Next, we move to 2

S: 
S still empty








V: 102
After this no place for 2 to go so it goes out of the DFS
Now it goes back to 0. Now from 0, we can also move to 3
Hence, our next vertex visited is 3

S: 2









V: 1023
now we move to vertex 4

S: 2









V: 10234

Now since all are over we retrace back.
We move to 3 and add 4 in the stack
S: 24
V:10234
Now we retrace back to 0 and add 3 to stack
S:243
V:10234
We now retrace back to 1 and add 0
S: 2430
V:10234
We now move out of the loop
S: 24301
V: 10234


Hence now it is our responsibility we need to reverse the graph as below

S: 24301
V:








Now we pop our first value from the stack and choose it as our starting element for DFS()
S.pop()=1
So we add 1 to our visited data structure.

S: 2430
V: 1
output: 1-







Next, DFS is 2

S: 2430
V: 12
output 1-2-







next DFS is 0

    

S: 2430
V: 120
output 1-2-0-
Next no more DFS possible so retrace back
'2' also has got no more paths to go so retrace back to '1'
Now '1' also has got no path to go so retrace back
Now S.pop()=0
but 0 is already visited hence continued
S: 243
V:120
output: 1-2-0-

S.pop()=3
'3' is not visited until now. So next we DFS for '3'

S: 24
V: 1203
output
1-2-0-
3-





Next, there is no path to go hence it retraces back

Next S.pop()=4 which is not visited till now

S: 2
V:12034
output:
1-2-0-
3-
4-




Next, there is no place for 4 to go which is not visited
hence retraces back
S.pop()=2
but 2 is already visited hence ignored
hence final status
S: empty
V: 12034
output:
1-2-0-
3-
4-
hence this is our required output