Kosaraju’s algorithm is a two-pass method to find all strongly connected components in a directed graph. A strongly connected component is a maximal subgraph where every vertex is reachable from every other vertex in that component.<\/p>\n\n\n\n
Steps of the algorithm:<\/strong><\/p>\n\n\n\n When you run the program, you should expect the output to look something like this:<\/p>\n\n\n\n This output shows the strongly connected components of the given directed graph. Each component is printed separately.<\/p>\n\n\n\n Kosaraju\u2019s algorithm is efficient and elegant for finding SCCs in directed graphs. By understanding the two-pass DFS and the importance of graph transposition, we can effectively break down complex graphs into their strongly connected components.<\/p>\n\n
\n
\n
\n
Implementation in C<\/h3>\n\n\n
\n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX 100\n\n\/\/ Structure to represent a graph\nstruct Graph {\n int V; \/\/ Number of vertices\n int adj[MAX][MAX]; \/\/ Adjacency matrix\n};\n\n\/\/ Stack structure for DFS\nint stack[MAX], top = -1;\n\n\/\/ Function to push element onto stack\nvoid push(int vertex) {\n stack[++top] = vertex;\n}\n\n\/\/ Function to pop element from stack\nint pop() {\n return stack[top--];\n}\n\n\/\/ Function to initialize the graph\nstruct Graph* createGraph(int vertices) {\n struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));\n graph->V = vertices;\n for (int i = 0; i < vertices; i++)\n for (int j = 0; j < vertices; j++)\n graph->adj[i][j] = 0; \/\/ Initialize adjacency matrix\n return graph;\n}\n\n\/\/ Function to add an edge to the graph\nvoid addEdge(struct Graph* graph, int src, int dest) {\n graph->adj[src][dest] = 1; \/\/ Directed edge from src to dest\n}\n\n\/\/ DFS function to fill the stack with vertices\nvoid dfs(struct Graph* graph, int vertex, int visited[]) {\n visited[vertex] = 1;\n for (int i = 0; i < graph->V; i++) {\n if (graph->adj[vertex][i] == 1 && !visited[i]) {\n dfs(graph, i, visited);\n }\n }\n push(vertex); \/\/ Push vertex to stack after exploring all its neighbors\n}\n\n\/\/ Transpose the graph\nstruct Graph* transposeGraph(struct Graph* graph) {\n struct Graph* transposed = createGraph(graph->V);\n for (int i = 0; i < graph->V; i++) {\n for (int j = 0; j < graph->V; j++) {\n if (graph->adj[i][j] == 1) {\n addEdge(transposed, j, i); \/\/ Reverse the edge\n }\n }\n }\n return transposed;\n}\n\n\/\/ DFS to find strongly connected components\nvoid dfsTransposed(struct Graph* transposed, int vertex, int visited[]) {\n visited[vertex] = 1;\n printf("%d ", vertex); \/\/ Print the vertex in the component\n for (int i = 0; i < transposed->V; i++) {\n if (transposed->adj[vertex][i] == 1 && !visited[i]) {\n dfsTransposed(transposed, i, visited);\n }\n }\n}\n\n\/\/ Function to find and print all strongly connected components\nvoid findSCCs(struct Graph* graph) {\n int visited[MAX] = {0};\n \n \/\/ First pass - fill vertices in stack according to finish time\n for (int i = 0; i < graph->V; i++) {\n if (!visited[i]) {\n dfs(graph, i, visited);\n }\n }\n\n \/\/ Transpose the graph\n struct Graph* transposed = transposeGraph(graph);\n\n \/\/ Second pass - process all vertices in order defined by the stack\n for (int i = 0; i < graph->V; i++) visited[i] = 0; \/\/ Reset visited array\n \n printf("Strongly Connected Components:\\n");\n while (top != -1) {\n int vertex = pop();\n if (!visited[vertex]) {\n printf("Component: ");\n dfsTransposed(transposed, vertex, visited);\n printf("\\n");\n }\n }\n}\n\n\/\/ Main function\nint main() {\n struct Graph* graph = createGraph(5); \/\/ Create a graph with 5 vertices\n addEdge(graph, 0, 1);\n addEdge(graph, 1, 2);\n addEdge(graph, 2, 0);\n addEdge(graph, 1, 3);\n addEdge(graph, 3, 4);\n\n findSCCs(graph);\n\n return 0;\n}\n\n<\/pre><\/div>\n\n\nExplanation of the Code<\/h3>\n\n\n\n
\n
\n
Graph<\/code> structure to hold the number of vertices and the adjacency matrix.<\/li>\n<\/ul>\n<\/li>\n\n\n\n\n
\n
dfs<\/code> function explores each vertex and pushes it onto the stack after exploring its neighbors.<\/li>\n\n\n\ndfsTransposed<\/code> function performs DFS on the transposed graph and prints the vertices of each strongly connected component.<\/li>\n<\/ul>\n<\/li>\n\n\n\n\n
transposeGraph<\/code> function creates a new graph where all edges are reversed.<\/li>\n<\/ul>\n<\/li>\n\n\n\n\n
findSCCs<\/code> function, we first fill the stack using a DFS on the original graph, transpose the graph, and then use another DFS based on the stack to identify and print each SCC.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\nInput Edges
<\/strong>In the main function, the following edges are added to the graph:
addEdge(graph, 0, 1); \/\/ Edge from vertex 0 to vertex 1
addEdge(graph, 1, 2); \/\/ Edge from vertex 1 to vertex 2
addEdge(graph, 2, 0); \/\/ Edge from vertex 2 to vertex 0 (forming a cycle)
addEdge(graph, 1, 3); \/\/ Edge from vertex 1 to vertex 3
addEdge(graph, 3, 4); \/\/ Edge from vertex 3 to vertex 4<\/pre>\n\n\n\nOutput<\/h3>\n\n\n\n
yamlCopy code
Strongly Connected Components:\nComponent: 4 \nComponent: 3 \nComponent: 2 1 0 \n<\/code><\/pre>\n\n\n\nConclusion<\/h3>\n\n\n\n