Overview of Kosaraju’s Algorithm
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.
Steps of the algorithm:
- First Pass (DFS on original graph):
- Perform a Depth-First Search (DFS) on the original graph to determine the finish order of nodes.
- Transpose the Graph:
- Reverse the direction of all edges in the graph.
- Second Pass (DFS on transposed graph):
- 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.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// Structure to represent a graph
struct Graph {
int V; // Number of vertices
int adj[MAX][MAX]; // Adjacency matrix
};
// Stack structure for DFS
int stack[MAX], top = -1;
// Function to push element onto stack
void push(int vertex) {
stack[++top] = vertex;
}
// Function to pop element from stack
int pop() {
return stack[top--];
}
// Function to initialize the graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = vertices;
for (int i = 0; i < vertices; i++)
for (int j = 0; j < vertices; j++)
graph->adj[i][j] = 0; // Initialize adjacency matrix
return graph;
}
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
graph->adj[src][dest] = 1; // Directed edge from src to dest
}
// DFS function to fill the stack with vertices
void dfs(struct Graph* graph, int vertex, int visited[]) {
visited[vertex] = 1;
for (int i = 0; i < graph->V; i++) {
if (graph->adj[vertex][i] == 1 && !visited[i]) {
dfs(graph, i, visited);
}
}
push(vertex); // Push vertex to stack after exploring all its neighbors
}
// Transpose the graph
struct Graph* transposeGraph(struct Graph* graph) {
struct Graph* transposed = createGraph(graph->V);
for (int i = 0; i < graph->V; i++) {
for (int j = 0; j < graph->V; j++) {
if (graph->adj[i][j] == 1) {
addEdge(transposed, j, i); // Reverse the edge
}
}
}
return transposed;
}
// DFS to find strongly connected components
void dfsTransposed(struct Graph* transposed, int vertex, int visited[]) {
visited[vertex] = 1;
printf("%d ", vertex); // Print the vertex in the component
for (int i = 0; i < transposed->V; i++) {
if (transposed->adj[vertex][i] == 1 && !visited[i]) {
dfsTransposed(transposed, i, visited);
}
}
}
// Function to find and print all strongly connected components
void findSCCs(struct Graph* graph) {
int visited[MAX] = {0};
// First pass - fill vertices in stack according to finish time
for (int i = 0; i < graph->V; i++) {
if (!visited[i]) {
dfs(graph, i, visited);
}
}
// Transpose the graph
struct Graph* transposed = transposeGraph(graph);
// Second pass - process all vertices in order defined by the stack
for (int i = 0; i < graph->V; i++) visited[i] = 0; // Reset visited array
printf("Strongly Connected Components:\n");
while (top != -1) {
int vertex = pop();
if (!visited[vertex]) {
printf("Component: ");
dfsTransposed(transposed, vertex, visited);
printf("\n");
}
}
}
// Main function
int main() {
struct Graph* graph = createGraph(5); // Create a graph with 5 vertices
addEdge(graph, 0, 1);
addEdge(graph, 1, 2);
addEdge(graph, 2, 0);
addEdge(graph, 1, 3);
addEdge(graph, 3, 4);
findSCCs(graph);
return 0;
}
Explanation of the Code
- Graph Representation:
- The graph is represented using an adjacency matrix. We define a
Graphstructure to hold the number of vertices and the adjacency matrix.
- The graph is represented using an adjacency matrix. We define a
- Stack Operations:
- We use a simple stack to store vertices based on their finishing times during DFS.
- DFS Implementation:
- The
dfsfunction explores each vertex and pushes it onto the stack after exploring its neighbors. - The
dfsTransposedfunction performs DFS on the transposed graph and prints the vertices of each strongly connected component.
- The
- Transposing the Graph:
- The
transposeGraphfunction creates a new graph where all edges are reversed.
- The
- Finding SCCs:
- In the
findSCCsfunction, 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.
- In the
Input Edges
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
Output
When you run the program, you should expect the output to look something like this:
yamlCopy codeStrongly Connected Components:
Component: 4
Component: 3
Component: 2 1 0
This output shows the strongly connected components of the given directed graph. Each component is printed separately.
Conclusion
Kosaraju’s 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.
