A directed graph is considered strongly connected if it allows traversal from any vertex to any other vertex within the same component. It is possible for a single directed graph to contain several strongly connected components. Graph connectivity pertains to the ability for two vertices to be reachable from each other. When defining connectivity based on paths, it implies that two vertices are connected if a path is present from one vertex to another.
Kosaraju's algorithm operates on a directed graph, utilizing depth-first search (DFS) to identify every Strongly Connected Component (SCC) within the graph. Its effectiveness stems from its ability to consolidate all connected vertices into a unified SCC. Essentially, the algorithm exhaustively detects all SCCs in the graph and provides a subgraph encompassing all reachable vertices.
The algorithm works in two main phases.
- Run a DFS on the original graph and push the vertices in a stack because they are finished or marked as back in the backtracking. We do not find the SCCs for the original graph in this step; we just find the finish times.
- Reverse the direction of all the edges in the graph, and then run it again using the same DFS process as before: First, reset all the finish times of all the vertices that we saved in the first step. After this step, each subsequent call to this DFS will return one SCC.
The procedure for applying Kosaraju's algorithm to identify all strongly connected components of a directed graph is detailed as follows:
Steps:
- Perform a depth-first search (DFS) traversal of the directed graph being considered with an empty stack (or any type of data structure that allows for DFS). The search operation is performed on the vertices.
- After that, Reverse the direction of each edge in the graph to get a new graph with the same vertices but in reversed directions. This direction reversal can be done by switching the source vertex to the destination vertex for each edge.
- Next, begin taking vertices off the stack one by one, and then perform DFS on the reversed graph for each vertex popped off the stack. After performing DFS on each vertex popped off the stack, the set of vertices reached together in a single traversal/DFS will relate to the strongly connected component associated with the selected vertex.
- Continue to repeat step 3 until the stack is empty. Every time a DFS is performed for a vertex stacked, there will be a new strongly connected component associated with the vertex popped from the stack.
- Kosaraju's method returned the extra new strongly connected components from a DFS traversal on the reversed graph in step 3. The components represent the strongly connected groups of vertices in the directed graph, and each strongly connected component is characterized by inter-vertex connectivity.
What is the use implement Kosaraju's algorithm?
Kosaraju's algorithm is utilized in directed graphs to identify strongly connected components. These components consist of vertices where each vertex can be reached from every other vertex within the same component through a directed path.
The considerations for applying Kosaraju's algorithm in directed graphs include:
- Time Complexity Efficiency: The time complexity of Kosaraju's algorithm is O(V + E), where V and E correspond to the number of vertices and edges in the directed graph. You emphasize that O(V + E) is linear time complexity, which makes Kosaraju's algorithm particularly compelling for use in not just large graphs but in real-world modelling situations where any persistent practical implementation will be a large graph.
- Simplicity and Implementability Iteration: Kosaraju's algorithm has very well-defined and simple instructions compared with other strongly connected component searching algorithms, such as Tarjan's or Gabow's. Kosaraju's algorithm is simply and aptly characterized as the two-phase depth-first-search (DFS) process, a DFS process followed by another DFS process but on the reverse directed graph.
- Finding Strongly Connected Components: As there are some distinct considerations for using Kosaraju's algorithm, you note that strongly connected components have widely desired applications in database management, network analysis, Social networks, or constructing a compiler. Finding strongly connected components displays the structure and behaviour of the information contained in directed graphs, but finding strongly connected components can also offer values engaged in practical problem-solving.
- Robust: Kosaraju's algorithm finds and identifies all strongly connected components in a directed graph, regardless of the directed graph being fully or partially disconnected. Kosaraju's algorithm will find strongly connected components regardless of whether the directed graph is fully partitioned or the vertices cannot be fully or partially reached from one another.
- Flexibility: The algorithm can be adapted for other-directed graph analytical and study purposes. For example, Kosaraju's algorithm could be adapted for use in directed graphs for k largest strongly connected components based on the number of vertices, or findings strongly connected components based on other conditional metrics.
Working of Kosaraju's Algorithm:
In directed graphs, Kosaraju's algorithm detects strong connected components (SCCs) efficiently. It consists of two main stages known as the Forward Stage and the Reverse Stage. Below is a broad explanation of the algorithm's functioning:
1. Forward Stage
Initiate the DFS traversal from an arbitrary vertex in the graph, assigning a "Finish time" to each vertex as it completes the depth-first search (DFS) process.
Create a list of vertices sorted by their completion time, typically stored in a vertex stack as they finish.
2. Reverse Stage
Reverse the orientation of every edge to transpose the graph, then remove vertices from the stack. Conduct a Depth-First Search (DFS) on the transposed graph. During this stage, the initial graph recognizes a strongly connected component that stems from the DFS traversal initiated at the popped vertex.
Example:
//Program to implement the Kosaraju's Algorithm in C
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
//The structure of the graph
struct Graph {
int vertex;
int adjM[MAX][MAX];
};
//The stack definition
struct Stack {
int item[MAX];
int peek; //top peek
};
// The function for creating Stack structure
struct Stack* creationOfStack() {
struct Stack* stacks= (struct Stack*)malloc(sizeof(struct Stack));
stacks->peek = -1;
return stacks;
}
// The function which is used for pushing
//element the element to the stack
void push(struct Stack* stacks, int val) {
stacks->item[++stacks->peek] = val;
}
// Function to remove an element from the stack
int pop(struct Stack* stacks) {
return stacks->item[stacks->peek--];
}
// Function to check if the stack is empty or not
int StackisEmpty(struct Stack* stacks) {
return stacks->peek== -1;
}
//Function to find the DFS search in the Graph
void dfs(struct Graph* g, int v, int visit[], struct Stack* stacks) {
visit[v] = 1;
for (int i = 0; i < g->vertex; i++) {
if (g->adjM[v][i] == 1 && !visit[i]) {
dfs(g, i, visit, stacks);
}
}
push(stacks, v);
}
// the Function to find the transpose of the given graph
struct Graph* getGraphTranspose(struct Graph* graph) {
struct Graph* trans= (struct Graph*)malloc(sizeof(struct Graph));
trans->vertex = graph->vertex;
for (int i = 0; i < graph->vertex; i++) {
for (int j = 0; j < graph->vertex; j++) {
trans->adjM[i][j] = graph->adjM[j][i];
}
}
return trans;
}
// The DFS operation on the Transposed Matrix
void dfsTransposeGraph(struct Graph* graph, int v, int visit[]) {
visit[v] = 1;
printf("%d ", v);
for (int i = 0; i < graph->vertex; i++) {
if (graph->adjM[v][i] == 1 && !visit[i]) {
dfsTransposeGraph(graph, i, visit);
}
}
}
// The function for determining the strongly connected components
void kosarajuAlgo(struct Graph* graph) {
struct Stack* stacks = creationOfStack();
int visit[MAX] = {0};
// The vertices are filled based on completion time
for (int i = 0; i < graph->vertex; i++) {
if (!visit[i]) {
dfs(graph, i, visit, stacks);
}
}
//2. Transposed Graph
struct Graph* trans= getGraphTranspose(graph);
//3. DFS operation on the transposed matrix
for (int i = 0; i < graph->vertex; i++) {
visit[i] = 0; //reset Value
}
printf("The Strongly Connected components of the graph are:\n");
while (!StackisEmpty(stacks)) {
int v = pop(stacks);
if (!visit[v]) {
dfsTransposeGraph(trans, v, visit);
printf("\n");
}
}
free(stacks);
free(trans);
}
// Main function
int main() {
struct Graph graphs;
graphs.vertex= 5;
// The matrix initialisation
for (int i = 0; i < graphs.vertex; i++) {
for (int j = 0; j < graphs.vertex; j++) {
graphs.adjM[i][j] = 0;
}
}
// Adding edges of the graph
graphs.adjM[0][1] = 1;
graphs.adjM[1][2] = 1;
graphs.adjM[2][0] = 1;
graphs.adjM[1][3] = 1;
graphs.adjM[3][4] = 1;
kosarajuAlgo(&graphs);
return 0;
}
Output:
The Strongly Connected components of the graph are:
0 2 1
3
4
Explanation:
Approach:
The functions outlined below are employed to determine the Strongest Connected Components.
Graph Structure:
The Graph data structure graph is established with the following components:
-
- Integer vertex: This signifies the total count of vertices within the graph.
-
- Integer adjMMAX: A 2D array serving as an adjacency matrix to depict the connections between vertices, where the constant MAX determines the maximum vertex capacity.
Stack Organization: The stack organization is employed to maintain the sequence of vertices while performing DFS traversal.
- Integer element[MAX]: A collection designated for holding all elements of the stack.
- Integer top: An integer value that signifies the top position within the stack. At the beginning, -1 is assigned to denote an empty stack.
- The code uses few functions to perform the required algorithm:
- Creation of Stack: Function(creationOfStack) will be used to create a new stack, it allocates the memory to the stack and initializes the peek index to -1.
- Push the item and Pop the item: Push and pop process elements to be pushed and pop. The push function will be used to push a vertex in the stack by increasing the peek index, while the function pop will be used to pop the vertex from the stack and decrease the peek index.
- Check if Stack is Empty: The StackisEmpty will be used to check if the stack is empty.
Functions:
The function dfs should be developed to execute Depth-First-Search on the initial graph. Indicate the current vertex as visited.
- Graph Transposition: Utilize the Function getGraphTranspose to transpose the graph.
- DFS on Transposed Graph: Analogous to the initial DFS, we will carry out the DFS function on the transposed graph.
Kosaraju's Algorithm:
The core function, kosarajuAlgo, runs the algorithm:
- First DFS call: It iterates over all vertices and calls the dfsfunction to fill the stack based on finishing times.
- Transpose the graph: It calls getGraphTransposeto create a transposed graph.
- Reset visited array: We reset the visited array to keep track of the second DFS accurately.
- Second DFS call: It pops vertices from the stack and calls dfsTransposeGraphfor the unvisited vertices discovered in the pop. It allows us to find and print the SCCs.
Main Function:
Specifies the quantity of vertices. Sets the adjacency matrix to zero as a starting point. Then, incorporates directed edges to the graph based on the provided information. Lastly, executes the kosarajuAlgo function to implement the algorithm and display the Strongly Connected Components it identifies.
Conclusion:
In summary, Kosaraju's Algorithm is a proficient and productive approach for identifying Strongly Connected Components (SCCs) within directed graphs. Operating with a time complexity of O(V + E), this technique is especially valuable for handling sizable graphs, showcasing its relevance in various practical scenarios like social network analysis, web crawling, and network routing.
Kosaraju's algorithm, a straightforward and adaptable approach, involves two depth-first searches (DFS) on the directed graph. Through graph reversal and stack implementation to establish the vertex processing sequence, the algorithm effectively detects Strongly Connected Components (SCCs) even in cases where the directed graph lacks connectivity.