Strongly Connected Components Data Structures and Algorithms

Algorithm

Strongly Connected Components (SCCs) are a concept in graph theory that arise in the context of directed graphs. In a directed graph, an SCC is a subset of vertices in which there is a directed path from every vertex to every other vertex within the subset.

Formally, an SCC in a directed graph $G$ is a maximal set of vertices $C$ such that for every pair of vertices $u$ and $v$ in $C$ , there is a directed path from $u$ to $v$ and a directed path from $v$ to $u$ within $C$ .

Finding strongly connected components is a fundamental algorithmic problem with applications in various areas, including compiler optimization, network analysis, and modeling systems with concurrency.

The most common algorithm used to find strongly connected components is Kosaraju's algorithm, which consists of two depth-first search (DFS) passes. Here's a high-level overview of the algorithm:

First Pass (DFS on Reverse Graph):
- Perform a DFS on the reverse graph (i.e., all edges reversed) to compute finishing times for each vertex. This step assigns a postorder number to each vertex.
Second Pass (DFS on Original Graph):
- Start DFS on the original graph in decreasing order of finishing times obtained from the first pass.
- Each DFS traversal from an unvisited vertex in this order identifies a strongly connected component.

The algorithm's correctness relies on the fact that the second DFS pass can reveal the strongly connected components by exploring vertices in reverse topological order based on finishing times.

The time complexity of Kosaraju's algorithm is $O (V + E)$ , where $V$ is the number of vertices and $E$ is the number of edges in the graph.

Other algorithms for finding strongly connected components include Tarjan's algorithm, which also uses a single DFS pass.

In summary, strongly connected components provide a way to analyze the connectivity structure of directed graphs and can be efficiently computed using algorithms like Kosaraju's or Tarjan's.

Code Examples

#1 Strongly Connected Components implement in Python

Code - Python Programming

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def dfs(self, vertex, visited, stack):
        visited[vertex] = True
        for neighbor in self.graph[vertex]:
            if not visited[neighbor]:
                self.dfs(neighbor, visited, stack)
        stack.append(vertex)

    def transpose(self):
        transposed_graph = Graph(self.vertices)
        for vertex in self.graph:
            for neighbor in self.graph[vertex]:
                transposed_graph.add_edge(neighbor, vertex)
        return transposed_graph

    def dfs_scc(self, vertex, visited, scc):
        visited[vertex] = True
        scc.append(vertex)
        for neighbor in self.graph[vertex]:
            if not visited[neighbor]:
                self.dfs_scc(neighbor, visited, scc)

    def kosaraju_scc(self):
        stack = []
        visited = [False] * self.vertices

        for vertex in range(self.vertices):
            if not visited[vertex]:
                self.dfs(vertex, visited, stack)

        transposed_graph = self.transpose()

        visited = [False] * self.vertices
        strongly_connected_components = []

        while stack:
            vertex = stack.pop()
            if not visited[vertex]:
                scc = []
                transposed_graph.dfs_scc(vertex, visited, scc)
                strongly_connected_components.append(scc)

        return strongly_connected_components

# Example usage:
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(1, 3)
g.add_edge(3, 4)

scc_result = g.kosaraju_scc()
print("Strongly Connected Components:")
print(scc_result)

Copy The Code & Try With Live Editor

#2 Strongly Connected Components implement in Java

Code - Java Programming

import java.util.*;

class Graph {
    private int V;
    private LinkedList < Integer>[] adj;

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i  <  v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void fillOrder(int v, boolean visited[], Stack < Integer> stack) {
        visited[v] = true;

        for (Integer neighbor : adj[v])
            if (!visited[neighbor])
                fillOrder(neighbor, visited, stack);

        stack.push(v);
    }

    Graph getTranspose() {
        Graph g = new Graph(V);
        for (int v = 0; v  <  V; v++) {
            for (Integer neighbor : adj[v]) {
                g.addEdge(neighbor, v);
            }
        }
        return g;
    }

    void DFS(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        for (Integer neighbor : adj[v]) {
            if (!visited[neighbor]) {
                DFS(neighbor, visited);
            }
        }
    }

    void printSCCs() {
        Stack < Integer> stack = new Stack<>();

        boolean[] visited = new boolean[V];
        for (int i = 0; i  <  V; i++)
            visited[i] = false;

        for (int i = 0; i  <  V; i++)
            if (!visited[i])
                fillOrder(i, visited, stack);

        Graph transposedGraph = getTranspose();

        for (int i = 0; i  <  V; i++)
            visited[i] = false;

        while (!stack.isEmpty()) {
            int v = stack.pop();

            if (!visited[v]) {
                transposedGraph.DFS(v, visited);
                System.out.println();
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(1, 3);
        g.addEdge(3, 4);

        System.out.println("Strongly Connected Components:");
        g.printSCCs();
    }
}

Copy The Code & Try With Live Editor

#3 Strongly Connected Components implement in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 1000

struct Node {
    int data;
    struct Node* next;
};

struct Graph {
    int vertices;
    struct Node** adjacency_list;
};

struct Stack {
    int* items;
    int top;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->items = (int*)malloc(sizeof(int) * capacity);
    stack->top = -1;
    return stack;
}

struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    graph->adjacency_list = (struct Node**)malloc(sizeof(struct Node*) * vertices);

    for (int i = 0; i  <  vertices; ++i) {
        graph->adjacency_list[i] = NULL;
    }

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjacency_list[src];
    graph->adjacency_list[src] = newNode;
}

void fillOrder(struct Graph* graph, int vertex, int* visited, struct Stack* stack) {
    visited[vertex] = 1;

    struct Node* current = graph->adjacency_list[vertex];
    while (current != NULL) {
        if (!visited[current->data]) {
            fillOrder(graph, current->data, visited, stack);
        }
        current = current->next;
    }

    push(stack, vertex);
}

struct Graph* getTranspose(struct Graph* graph) {
    struct Graph* transposedGraph = createGraph(graph->vertices);

    for (int v = 0; v  <  graph->vertices; v++) {
        struct Node* current = graph->adjacency_list[v];
        while (current != NULL) {
            addEdge(transposedGraph, current->data, v);
            current = current->next;
        }
    }

    return transposedGraph;
}

void DFS(struct Graph* graph, int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    struct Node* current = graph->adjacency_list[vertex];
    while (current != NULL) {
        if (!visited[current->data]) {
            DFS(graph, current->data, visited);
        }
        current = current->next;
    }
}

void printSCCs(struct Graph* graph) {
    struct Stack* stack = createStack(graph->vertices);
    int* visited = (int*)malloc(sizeof(int) * graph->vertices);

    for (int i = 0; i  <  graph->vertices; i++) {
        visited[i] = 0;
    }

    for (int i = 0; i  <  graph->vertices; i++) {
        if (!visited[i]) {
            fillOrder(graph, i, visited, stack);
        }
    }

    struct Graph* transposedGraph = getTranspose(graph);

    for (int i = 0; i  <  graph->vertices; i++) {
        visited[i] = 0;
    }

    while (stack->top != -1) {
        int vertex = pop(stack);

        if (!visited[vertex]) {
            printf("SCC: ");
            DFS(transposedGraph, vertex, visited);
            printf("\n");
        }
    }
}

void push(struct Stack* stack, int item) {
    stack->items[++stack->top] = item;
}

int pop(struct Stack* stack) {
    return stack->items[stack->top--];
}

int main() {
    int vertices, edges;
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);

    struct Graph* graph = createGraph(vertices);

    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    printf("Enter the edges (source destination):\n");
    for (int i = 0; i  <  edges; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    printf("Strongly Connected Components:\n");
    printSCCs(graph);

    return 0;
}

Copy The Code & Try With Live Editor

#4 Strongly Connected Components implement in C++

Code - C++ Programming

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

class Graph {
    int V; // Number of vertices
    vector < vector<int>> adj; // Adjacency list

public:
    Graph(int vertices) : V(vertices), adj(vertices) {}

    // Add edge to the graph
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    // DFS to fill stack with vertices in increasing order of finishing times
    void fillOrder(int v, vector < bool>& visited, stack<int>& stack) {
        visited[v] = true;
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                fillOrder(neighbor, visited, stack);
            }
        }
        stack.push(v);
    }

    // Transpose the graph (reverse all edges)
    Graph getTranspose() {
        Graph gT(V);
        for (int v = 0; v  <  V; ++v) {
            for (int neighbor : adj[v]) {
                gT.addEdge(neighbor, v);
            }
        }
        return gT;
    }

    // DFS to explore a SCC
    void DFS(int v, vector < bool>& visited, vector<int>& scc) {
        visited[v] = true;
        scc.push_back(v);
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                DFS(neighbor, visited, scc);
            }
        }
    }

    // Function to find strongly connected components
    void printSCCs() {
        stack < int> stack;
        vector<bool> visited(V, false);

        // Fill vertices in stack according to their finishing times
        for (int v = 0; v  <  V; ++v) {
            if (!visited[v]) {
                fillOrder(v, visited, stack);
            }
        }

        // Transpose the graph
        Graph gT = getTranspose();

        // Reset visited array for the second DFS
        fill(visited.begin(), visited.end(), false);

        // Process vertices in decreasing order of finishing times
        while (!stack.empty()) {
            int v = stack.top();
            stack.pop();

            if (!visited[v]) {
                vector<int> scc;
                gT.DFS(v, visited, scc);

                // Print the current SCC
                cout << "SCC:";
                for (int vertex : scc) {
                    cout << " " << vertex;
                }
                cout << endl;
            }
        }
    }
};

int main() {
    // Create a graph
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(1, 3);
    g.addEdge(3, 4);

    // Print SCCs
    cout << "Strongly Connected Components:\n";
    g.printSCCs();

    return 0;
}

Copy The Code & Try With Live Editor

Demonstration

Strongly Connected Components Data Structures and Algorithms

Try With Live Editor

Category - Data Structure and Algorithm Maniruzzaman Akash 1 year ago 270 0