{"id":660,"date":"2024-10-10T13:39:37","date_gmt":"2024-10-10T08:09:37","guid":{"rendered":"https:\/\/codexplained.in\/?p=660"},"modified":"2025-11-24T15:58:49","modified_gmt":"2025-11-24T10:28:49","slug":"find-strongly-connected-components-kosarajus-algorithm","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=660","title":{"rendered":"Find Powerfully Connected Components using Kosaraju\u2019s Algorithm"},"content":{"rendered":"\n

Overview of Kosaraju\u2019s Algorithm<\/h3>\n\n\n\n

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

    \n
  1. First Pass (DFS on original graph):<\/strong>\n
      \n
    • Perform a Depth-First Search (DFS) on the original graph to determine the finish order of nodes.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • Transpose the Graph:<\/strong>\n
        \n
      • Reverse the direction of all edges in the graph.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Second Pass (DFS on transposed graph):<\/strong>\n
          \n
        • Perform DFS on the transposed graph in the order of decreasing finish times obtained from the first pass. Each DFS call will identify one strongly connected component.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\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\n
          Explanation of the Code<\/h3>\n\n\n\n
            \n
          1. Graph Representation:<\/strong>\n
              \n
            • The graph is represented using an adjacency matrix. We define a Graph<\/code> structure to hold the number of vertices and the adjacency matrix.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Stack Operations:<\/strong>\n
                \n
              • We use a simple stack to store vertices based on their finishing times during DFS.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
              • DFS Implementation:<\/strong>\n
                  \n
                • The dfs<\/code> function explores each vertex and pushes it onto the stack after exploring its neighbors.<\/li>\n\n\n\n
                • The dfsTransposed<\/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
                • Transposing the Graph:<\/strong>\n
                    \n
                  • The transposeGraph<\/code> function creates a new graph where all edges are reversed.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                  • Finding SCCs:<\/strong>\n
                      \n
                    • In the 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\n
                      Input 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\n
                      Output<\/h3>\n\n\n\n
                      When you run the program, you should expect the output to look something like this:<\/p>\n\n\n\n
                      yamlCopy codeStrongly Connected Components:\nComponent: 4 \nComponent: 3 \nComponent: 2 1 0 \n<\/code><\/pre>\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
                      Conclusion<\/h3>\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