Strongly Connected Components (SCC) & Bridges in Graphs

Strongly Connected Components (SCC)

A Strongly Connected Component of a directed graph is a maximal group of vertices where each vertex is reachable from any other vertex in the same group.

Kosaraju's Algorithm for SCC

• Perform a DFS to get vertices in finishing time order.
• Transpose the graph (reverse direction of edges).
• Perform DFS in order of decreasing finishing times on transposed graph, each DFS produces one SCC.
• Time complexity: O(V + E).

Python Code for SCC (Kosaraju's Algorithm)

from collections import defaultdict

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

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

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

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

    def transpose(self):
        g = Graph(self.V)
        for v in self.graph:
            for neighbor in self.graph[v]:
                g.add_edge(neighbor, v)
        return g

    def print_scc(self):
        stack = []
        visited = [False] * self.V

        for i in range(self.V):
            if not visited[i]:
                self.fill_order(i, visited, stack)

        transpose_graph = self.transpose()
        visited = [False] * self.V

        print("Strongly Connected Components:")
        while stack:
            v = stack.pop()
            if not visited[v]:
                scc_stack = []
                transpose_graph.dfs(v, visited, scc_stack)
                print(scc_stack)

# Usage
g = Graph(8)
edges = [(0,1),(1,2),(2,3),(2,4),(3,0),(4,5),(5,6),(6,4),(6,7)]
for u, v in edges:
    g.add_edge(u, v)
g.print_scc()

Bridges in Graphs

A bridge (or cut-edge) in an undirected graph is an edge which, when removed, increases the number of connected components.

Finding Bridges using DFS

• Use DFS traversal recording discovery time and lowest reachable vertex.
• If there is no back edge from the adjacent vertices, then the edge is a bridge.
• Time complexity: O(V + E).

Python Code to Find Bridges

def dfs_bridges(u, visited, parent, disc, low, time, graph, bridges):
    visited[u] = True
    disc[u] = low[u] = time[0]
    time[0] += 1

    for v in graph[u]:
        if not visited[v]:
            parent[v] = u
            dfs_bridges(v, visited, parent, disc, low, time, graph, bridges)
            low[u] = min(low[u], low[v])

            if low[v] > disc[u]:
                bridges.append((u, v))
        elif v != parent[u]:
            low[u] = min(low[u], disc[v])

def find_bridges(V, edges):
    graph = [[] for _ in range(V)]
    for u,v in edges:
        graph[u].append(v)
        graph[v].append(u)  # undirected

    visited = [False] * V
    disc = [float('inf')] * V
    low = [float('inf')] * V
    parent = [-1] * V
    time = [0]
    bridges = []

    for i in range(V):
        if not visited[i]:
            dfs_bridges(i, visited, parent, disc, low, time, graph, bridges)

    return bridges

# Usage
V = 5
edges = [(1, 0), (0, 2), (2, 1), (0, 3), (3, 4)]
print("Bridges in graph:", find_bridges(V, edges))