Strongly Connected Components

Strongly Connected Components (SCCs) are specific sub-graphs in a directed graph where every node can reach every other node within that sub-graph. In simple terms, SCCs are clusters of nodes that are tightly connected but are separate from other parts of the graph. Understanding SCCs is important, as they help in detecting cycles and studying network structures.

A directed graph is said to be strongly connected if every node can reach every other node directly or indirectly. However, in larger graphs, we may have multiple strongly connected parts that are not connected to each other. These independent sections are called strongly connected components.

For example, consider a directed graph with nodes A, B, C, D, and E. If A can reach B and B can reach A, but C, D, and E form a separate cluster where they can all reach each other but not A or B, then there are two SCCs in the graph: {A, B} and {C, D, E}.

Strongly Connected Components Algorithm

There are two popular algorithms to find strongly connected components in a graph:

• Kosaraju's Algorithm
• Tarjan's Algorithm

Kosaraju's Algorithm

Kosaraju's Algorithm is a two-pass algorithm that finds strongly connected components in a directed graph. Here's how it works:

• First Pass: Perform a Depth First Search (DFS) on the graph and store the order of nodes based on their finishing times.
• Second Pass: Reverse the graph and perform another DFS on the nodes in the order of their finishing times from the first pass. This will give us the strongly connected components.

Kosaraju's Algorithm Example

Let's consider a directed graph with nodes A, B, C, D, and E, and the following edges:

 A -> B B -> C C -> A C -> D D -> E E -> D 

Using Kosaraju's Algorithm, we can find the strongly connected components in the graph:

• First Pass: The finishing times of the nodes are E, D, C, B, A.
• Second Pass: The strongly connected components are {A, B, C} and {D, E}.

Code for Kosaraju's Algorithm

Here's an example code snippet for Kosaraju's Algorithm in C, C++, Java, and Python:

 #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_VERTICES 5 // Graph adjacency matrix int adj[MAX_VERTICES][MAX_VERTICES] = { {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {1, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0} }; int visited[MAX_VERTICES] = {0}; int finishing_time[MAX_VERTICES]; int finish_index = 0; // Mapping index to letters (A-E) char map[MAX_VERTICES] = {'A', 'B', 'C', 'D', 'E'}; void DFS(int vertex, int print) { visited[vertex] = 1; if (print) printf("%c ", map[vertex]); // Print vertex if it's in SCC traversal for (int v = 0; v < MAX_VERTICES; v++) { if (adj[vertex][v] && !visited[v]) { DFS(v, print); } } if (!print) finishing_time[finish_index++] = vertex; // Store finishing time if not printing SCC } void reverse_graph() { int temp[MAX_VERTICES][MAX_VERTICES]; for (int i = 0; i < MAX_VERTICES; i++) { for (int j = 0; j < MAX_VERTICES; j++) { temp[i][j] = adj[i][j]; } } // Transpose the graph for (int i = 0; i < MAX_VERTICES; i++) { for (int j = 0; j < MAX_VERTICES; j++) { adj[i][j] = temp[j][i]; } } } void find_scc() { // Step 1: Compute finishing times in the original graph for (int v = 0; v < MAX_VERTICES; v++) { if (!visited[v]) { DFS(v, 0); // First pass DFS (store finish times) } } // Step 2: Reverse the graph reverse_graph(); // Step 3: Second DFS based on decreasing finishing times memset(visited, 0, sizeof(visited)); // Reset visited array printf("Strongly Connected Components:\n"); for (int i = MAX_VERTICES - 1; i >= 0; i--) { int vertex = finishing_time[i]; if (!visited[vertex]) { printf("SCC: "); DFS(vertex, 1); // Second pass DFS (print SCC) printf("\n"); } } } int main() { find_scc(); return 0; } 

 Strongly Connected Components: SCC: A C B SCC: D E 

 #include <iostream> #include <cstring> using namespace std; #define MAX_VERTICES 5 // Graph adjacency matrix int adj[MAX_VERTICES][MAX_VERTICES] = { {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {1, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0} }; int visited[MAX_VERTICES] = {0}; int finishing_time[MAX_VERTICES]; int finish_index = 0; // Mapping index to letters (A-E) char map[MAX_VERTICES] = {'A', 'B', 'C', 'D', 'E'}; void DFS(int vertex, int print) { visited[vertex] = 1; if (print) cout << map[vertex] << " "; // Print vertex if it's in SCC traversal for (int v = 0; v < MAX_VERTICES; v++) { if (adj[vertex][v] && !visited[v]) { DFS(v, print); } } if (!print) finishing_time[finish_index++] = vertex; // Store finishing time if not printing SCC } void reverse_graph() { int temp[MAX_VERTICES][MAX_VERTICES]; for (int i = 0; i < MAX_VERTICES; i++) { for (int j = 0; j < MAX_VERTICES; j++) { temp[i][j] = adj[i][j]; } } // Transpose the graph for (int i = 0; i < MAX_VERTICES; i++) { for (int j = 0; j < MAX_VERTICES; j++) { adj[i][j] = temp[j][i]; } } } void find_scc() { // Step 1: Compute finishing times in the original graph for (int v = 0; v < MAX_VERTICES; v++) { if (!visited[v]) { DFS(v, 0); // First pass DFS (store finish times) } } // Step 2: Reverse the graph reverse_graph(); // Step 3: Second DFS based on decreasing finishing times memset(visited, 0, sizeof(visited)); // Reset visited array cout << "Strongly Connected Components:" << endl; for (int i = MAX_VERTICES - 1; i >= 0; i--) { int vertex = finishing_time[i]; if (!visited[vertex]) { cout << "SCC: "; DFS(vertex, 1); // Second pass DFS (print SCC) cout << endl; } } } int main() { find_scc(); return 0; } 

 Strongly Connected Components: SCC: A C B SCC: D E 

 public class StronglyConnectedComponents { static final int MAX_VERTICES = 5; static int[][] adj = { {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {1, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0} }; static int[] visited = new int[MAX_VERTICES]; static int[] finishing_time = new int[MAX_VERTICES]; static int finish_index = 0; static char[] map = {'A', 'B', 'C', 'D', 'E'}; static void DFS(int vertex, boolean recordFinishTime) { visited[vertex] = 1; if (!recordFinishTime) { System.out.print(map[vertex] + " "); } for (int v = 0; v < MAX_VERTICES; v++) { if (adj[vertex][v] == 1 && visited[v] == 0) { DFS(v, recordFinishTime); } } if (recordFinishTime) { finishing_time[finish_index++] = vertex; } } static void reverse_graph() { int[][] temp = new int[MAX_VERTICES][MAX_VERTICES]; for (int i = 0; i < MAX_VERTICES; i++) { for (int j = 0; j < MAX_VERTICES; j++) { temp[i][j] = adj[j][i]; } } adj = temp; } static void find_scc() { for (int v = 0; v < MAX_VERTICES; v++) { if (visited[v] == 0) { DFS(v, true); } } reverse_graph(); visited = new int[MAX_VERTICES]; System.out.println("Strongly Connected Components:"); for (int i = MAX_VERTICES - 1; i >= 0; i--) { int vertex = finishing_time[i]; if (visited[vertex] == 0) { System.out.print("SCC: "); DFS(vertex, false); System.out.println(); } } } public static void main(String[] args) { find_scc(); } } 

 SCC: A C B SCC: D E 

 MAX_VERTICES = 5 # Graph adjacency matrix adj = [ [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [1, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 0, 0, 1, 0] ] visited = [False] * MAX_VERTICES finishing_time = [0] * MAX_VERTICES finish_index = 0 # Mapping index to letters (A-E) vertex_map = ['A', 'B', 'C', 'D', 'E'] def DFS(vertex, record_time): global finish_index # Declare as global to avoid UnboundLocalError visited[vertex] = True if not record_time: print(vertex_map[vertex], end=" ") # Print SCC members for v in range(MAX_VERTICES): if adj[vertex][v] and not visited[v]: DFS(v, record_time) if record_time: # Store finishing order in first DFS pass finishing_time[finish_index] = vertex finish_index += 1 def reverse_graph(): global adj adj = [[adj[j][i] for j in range(MAX_VERTICES)] for i in range(MAX_VERTICES)] def find_scc(): global visited, finish_index visited = [False] * MAX_VERTICES finish_index = 0 # First DFS pass to get finishing times for v in range(MAX_VERTICES): if not visited[v]: DFS(v, True) # Step 2: Reverse the graph reverse_graph() # Step 3: Second DFS based on decreasing finishing times visited = [False] * MAX_VERTICES print("Strongly Connected Components:") for i in range(MAX_VERTICES - 1, -1, -1): vertex = finishing_time[i] if not visited[vertex]: print("SCC:", end=" ") DFS(vertex, False) print() if __name__ == "__main__": find_scc() 

 SCC: A C B SCC: D E 

Tarjan's Algorithm

Tarjan's Algorithm is another popular algorithm to find strongly connected components in a directed graph. It uses Depth First Search (DFS) to traverse the graph and identify SCCs. Here's how it works:

• Initialize a stack to keep track of visited nodes and their order of traversal.
• Perform a DFS traversal of the graph, assigning a unique ID to each node and keeping track of the lowest ID reachable from that node.
• Nodes with the same ID and low-link value form a strongly connected component.

Tarjan's Algorithm Example

Consider the same directed graph with nodes A, B, C, D, and E, and the following edges:

 A -> B B -> C C -> A C -> D D -> E E -> D 

Using Tarjan's Algorithm, we can find the strongly connected components in the graph:

• The strongly connected components are {A, B, C} and {D, E}.

Code for Tarjan's Algorithm

Here's an example code snippet for Tarjan's Algorithm in C, C++, Java, and Python:

 #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_VERTICES 5 // Graph adjacency matrix int adj[MAX_VERTICES][MAX_VERTICES] = { {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {1, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0} }; int visited[MAX_VERTICES] = {0}; int stack[MAX_VERTICES]; int stack_index = 0; int ids[MAX_VERTICES]; int low[MAX_VERTICES]; int id = 0; // Mapping index to letters (A-E) char map[MAX_VERTICES] = {'A', 'B', 'C', 'D', 'E'}; int map_index = 0; void DFS(int vertex) { stack[stack_index++] = vertex; visited[vertex] = 1; ids[vertex] = low[vertex] = id++; for (int v = 0; v < MAX_VERTICES; v++) { if (adj[vertex][v]) { if (!visited[v]) { DFS(v); } if (ids[v] != -1) { low[vertex] = low[vertex] 0) { int node = stack[--stack_index]; low[node] = ids[vertex]; printf("%c ", map[node]); if (node == vertex) break; } printf("\n"); } } void find_scc() { memset(ids, -1, sizeof(ids)); memset(low, -1, sizeof(low)); for (int v = 0; v < MAX_VERTICES; v++) { if (!visited[v]) { DFS(v); } } } int main() { find_scc(); return 0; } 

 SCC: E D SCC: C B A 

 #include <iostream> #include <cstring> using namespace std; #define MAX_VERTICES 5 // Graph adjacency matrix int adj[MAX_VERTICES][MAX_VERTICES] = { {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {1, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0} }; int visited[MAX_VERTICES] = {0}; int stack[MAX_VERTICES]; int stack_index = 0; int ids[MAX_VERTICES]; int low[MAX_VERTICES]; int id = 0; // Mapping index to letters (A-E) char map[MAX_VERTICES] = {'A', 'B', 'C', 'D', 'E'}; int map_index = 0; void DFS(int vertex) { stack[stack_index++] = vertex; visited[vertex] = 1; ids[vertex] = low[vertex] = id++; for (int v = 0; v < MAX_VERTICES; v++) { if (adj[vertex][v]) { if (!visited[v]) { DFS(v); } if (ids[v] != -1) { low[vertex] = low[vertex] < low[v] ? low[vertex] : low[v]; } } } if (ids[vertex] == low[vertex]) { cout << "SCC: "; while (stack_index > 0) { int node = stack[--stack_index]; low[node] = ids[vertex]; cout << map[node] << " "; if (node == vertex) break; } cout << endl; } } void find_scc() { memset(ids, -1, sizeof(ids)); memset(low, -1, sizeof(low)); for (int v = 0; v < MAX_VERTICES; v++) { if (!visited[v]) { DFS(v); } } } int main() { find_scc(); return 0; } 

 SCC: E D SCC: C B A 

 public class TarjansAlgorithm { static final int MAX_VERTICES = 5; // Graph adjacency matrix static int[][] adj = { {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {1, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0} }; static int[] visited = new int[MAX_VERTICES]; static int[] stack = new int[MAX_VERTICES]; static int stack_index = 0; static int[] ids = new int[MAX_VERTICES]; static int[] low = new int[MAX_VERTICES]; static int id = 0; // Mapping index to letters (A-E) static char[] map = {'A', 'B', 'C', 'D', 'E'}; static int map_index = 0; static void DFS(int vertex) { stack[stack_index++] = vertex; visited[vertex] = 1; ids[vertex] = low[vertex] = id++; for (int v = 0; v < MAX_VERTICES; v++) { if (adj[vertex][v] == 1) { if (visited[v] == 0) { DFS(v); } if (ids[v] != -1) { low[vertex] = low[vertex] < low[v] ? low[vertex] : low[v]; } } } if (ids[vertex] == low[vertex]) { System.out.print("SCC: "); while (stack_index > 0) { int node = stack[--stack_index]; low[node] = ids[vertex]; System.out.print(map[node] + " "); if (node == vertex) break; } System.out.println(); } } static void find_scc() { for (int v = 0; v < MAX_VERTICES; v++) { if (visited[v] == 0) { DFS(v); } } } public static void main(String[] args) { find_scc(); } } 

 SCC: E D SCC: C B A 

 MAX_VERTICES = 5 adj = [ [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [1, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 0, 0, 1, 0] ] visited = [False] * MAX_VERTICES stack = [] on_stack = [False] * MAX_VERTICES ids = [-1] * MAX_VERTICES low = [-1] * MAX_VERTICES scc_count = 0 id = 0 map_index = ['A', 'B', 'C', 'D', 'E'] def DFS(vertex): global id, scc_count stack.append(vertex) on_stack[vertex] = True ids[vertex] = low[vertex] = id id += 1 for v in range(MAX_VERTICES): if adj[vertex][v] == 1: if ids[v] == -1: # Unvisited DFS(v) low[vertex] = min(low[vertex], low[v]) elif on_stack[v]: # In the current SCC low[vertex] = min(low[vertex], ids[v]) if ids[vertex] == low[vertex]: print("SCC:", end=" ") while True: node = stack.pop() on_stack[node] = False low[node] = ids[vertex] print(map_index[node], end=" ") if node == vertex: break print() scc_count += 1 def find_scc(): for v in range(MAX_VERTICES): if ids[v] == -1: DFS(v) find_scc() 

 SCC: E D SCC: C B A 

Applications of Strongly Connected Components

Following are some common applications of Strongly Connected Components:

• Network Analysis: SCCs help in understanding the structure and connectivity of networks, such as social networks, transportation networks, and communication networks.
• Graph Algorithms: SCCs are used in various graph algorithms, such as cycle detection, pathfinding, and network flow optimization.
• Software Engineering: SCCs are useful in software engineering for dependency analysis, module identification, and code refactoring.

Conclusion

Understanding Strongly Connected Components is essential for analyzing the connectivity and structure of directed graphs. Algorithms like Kosaraju's Algorithm and Tarjan's Algorithm provide efficient ways to identify SCCs in graphs, enabling various applications in network analysis, graph algorithms, and software engineering.