Strongly Connected Components Algorithm in C
In this article you will find out how Strongly Connected Components(SCC) are formed,explanation of Kosaraju’s algorithm to find SCC and algorithm implementation using C language.
A strongly connected component is a partition of a directed graph in which there is a path from each vertex to another vertex in the partition. This is applied only on Directed graphs.
For example following graph contains 3 SCCs :
We can find all the SCCs in a graph using Kosaraju’s algorithm in O(V+E) time(If the graph is described using an adjacency list). If the graph is represented as an adjacency matrix, the algorithm requires Ο(V²) time.This algorithm is DFS based and it does DFS two times.Let’s see how Kosaraju’s algorithm works.
Kosaraju’s Algorithm
Basically this algorithm involve 3 steps.
- Create an empty stack and perform depth first search on whole graph
Let’s start from vertex-0, then visit all of its child vertices, and mark them as visited. If a vertex leads to an already visited vertex, then push this vertex to the stack.
For example in Figure 1: Starting from vertex-0,go to vertex-2,vertex-1,then vertex-1 leads to vertex-0 which was already visited.So push the vertex-1 (current source vertex) to the stack.
Go to the previous vertex (vertex-2) and visit its child vertices if they exist. (In here vertex-2 do not have child vertices which are not visited already) Since push vertex-2 into the stack.
Then again go to the previous vertex (vertex-0) and it has child vertices which are not visited (vertex-3),visit vertex-3, go to vertex-4.Since there is nowhere to go from vertex-4, push it into the stack.
Again go to the previous vertex (vertex-3) and it has no child vertices which are not visited.Since push it to the stack.Then go to previous vertex (vertex-0) push it to the stack since it has no child vertices which are not visited already.
Then final stack is created and all the vertices are visited.
2. Reverse the direction of all edges and create the transpose graph
3. Perform depth first search on reversed graph
Start from the top vertex of the stack. Traverse through all of its child vertices until already visited vertex is reached, then one strongly connected component is formed.
For example in Figure 1: Pop vertex-0 from the stack. Starting from vertex-0, traverse through its child vertices (vertex-0, vertex-1, vertex-2 in sequence) and mark them as visited. The child of vertex-2 (vertex-0) is already visited, so these visited vertices form one strongly connected component.
Go to the stack and pop the top vertex if already visited. Otherwise, choose the top vertex from the stack and traverse through its child vertices as above.(In here top of stack has vertex-3 and it is not visited,pop vertex-3 and vertex-3 do not have child vertices even.Therefore vertex-3 form one strongly connected component.)
Similarly vertex-4 even form one strongly connected component.
Now again pop the top vertex(current top vertex is vertex-2) since it is already visited.Next top vertex is vertex-1 and it even already visited,therefore pop it.Now the stack is empty and all the vertices are visited.
And we are done finding all the SCCs.
Let’s move to the algorithm implementation in C
Here I implement a weighted directed graph, but it is not necessary for the any part of the algorithm(If you want, you can omit the weight and continue with directed graph)
Define libraries, structures to store data of stacks and graphs.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 5struct Graph *graph;
struct Graph *gr;
int stack[MAX_SIZE], top;// A structure to represent an adjacency list node
struct adj_list_node{
int dest;
int weight;
struct adj_list_node *next;
};// A structure to represent an adjacency list
struct adj_list{
struct adj_list_node *head;
};// A structure to represent a graph
struct Graph{
int V;
int *visited;
struct adj_list *array;
};
Declare functions to implement the graph, add edges to the graph, implement transpose graph, fill the stack and do DFS traversal
//*************START OF METHODS RELATED TO GRAPH**************// Function to create a new adjacency list node
struct adj_list_node *new_adj_list_node(int dest, int weight){struct adj_list_node *newNode = (struct adj_list_node *)malloc(sizeof(struct adj_list_node));newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}// Function to creates a graph with V vertices
struct Graph *create_graph(int V){struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct adj_list *)malloc(V * sizeof(struct adj_list));
int i;for (i = 0; i < V; ++i)
graph->array[i].head = NULL;return graph;
}// Fuction to add edges to graph
void add_edge(struct Graph *graph, struct Graph *gr, int src, int dest, int weight){struct adj_list_node *newNode = new_adj_list_node(dest, weight);newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
get_transpose(gr, src, dest, weight);
}// Function to print the graph
void print_graph(struct Graph *graph1){int v;
for (v = 0; v < graph1->V; ++v){
struct adj_list_node *temp = graph1->array[v].head;while (temp){
printf(“(%d -> %d(%d))\t”, v, temp->dest, temp->weight);
temp = temp->next;
}
}
}// Fuction to fill the stack
void set_fill_order(struct Graph *graph, int v, bool visited[], int *stack){visited[v] = true;
int i = 0;
struct adj_list_node *temp = graph->array[v].head;while (temp){
if (!visited[temp->dest])
{
set_fill_order(graph, temp->dest, visited, stack);
}
temp = temp->next;
}
push(v);
}// A recursive function to print DFS starting from v
void dfs_recursive(struct Graph *gr, int v, bool visited[]){visited[v] = true;
printf(“%d “, v);
struct adj_list_node *temp = gr->array[v].head;while (temp){
if (!visited[temp->dest]){
dfs_recursive(gr, temp->dest, visited);
}
temp = temp->next;
}
}// Fuction to add edges to transpose graph
void get_transpose(struct Graph *gr, int src, int dest, int weight){struct adj_list_node *newNode = new_adj_list_node(src, weight);
newNode->next = gr->array[dest].head;
gr->array[dest].head = newNode;
}//***************END OF METHODS RELATED TO GRAPH****************
Find the strongly connected components
//**********START OF STRONGLY CONNECTED COMPONENTS CHECK**********void strongly_connected_components(struct Graph *graph, struct Graph *gr, int V){bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;for (int i = 0; i < V; i++){
if (visited[i] == false){
set_fill_order(graph, i, visited, stack);
}
}int count = 1;
for (int i = 0; i < V; i++)
visited[i] = false;while (top != -1){
int v = stack[top];
pop();if (visited[v] == false){
printf(“Strongly connected component %d: \n”, count++);
dfs_recursive(gr, v, visited);
printf(“\n”);
}
}
}//****************END OF STRONGLY CONNECTED COMPONENTS CHECK***************
Functions to push and pop items from the stack
//***************START OF STACK FUNCTIONS**********************// Function to push item to stack
void push(int x){if (top >= MAX_SIZE — 1){
printf(“\n\tSTACK is over flow”);
}
else{
top++;
stack[top] = x;
}
}// Function to pop item to stack
void pop(){if (top <= -1){
printf(“\n\t Stack is under flow”);
}else{
top — ;
}
}//*****************END OF STACK FUNCTIONS**********************
Driver program to test above functions
int main(){top = -1;
int v = 5;struct Graph *graph = create_graph(v);
struct Graph *gr = create_graph(v);add_edge(graph, gr, 1, 0, 2);
add_edge(graph, gr, 0, 2, 2);
add_edge(graph, gr, 2, 1, 2);
add_edge(graph, gr, 0, 3, 2);
add_edge(graph, gr, 3, 4, 2);
strongly_connected_components(graph, gr, v);return 0;
}
Applications of Strongly connected components:
- Vehicle-routing applications
- Find connected groups in Social Networks
Try to implement the code by your own and visit my Github repository to find out my code.
Hope you understood the algorithm and the code implementation.
Thank you for reading!
