Strongly Connected Components Search

Python C++

  • Input:directed graph with N nodes and M edges
  • Output: array components of graph strongly connected components
  • Time complexity: $O(N + M)$


A directed graph is called strongly connected graph if there is a path in each direction between each pair of nodes of the graph

A strongly connected component of a directed graph G is a subgraph that is strongly connected, and is maximal with this property: no additional edges or nodes from G can be included in the subgraph without breaking its property of being strongly connected.

Description

Condensation order

Run sequence of depth first search of the graph which will return nodes with increasing exit time, i.e. some list condensation_order.

Strongly connected components

Build transposed_graph. Run a series of depth first searches in the order determined by list condensation_order (to be exact in reverse order, i.e. in decreasing order of exit times) on transposed_graph. Every set of nodes, reached after the next search, will be the next strongly connected component.

Example

Let's see how the Strongly Connected Components Search (SCCS) algorithm works with an example. We use an directed graph with 7 nodes.

SCCS starts from node 1 and set visited[1] = 1.

SCCS moves to node 4 and set visited[4] = 1.

SCCS moves to node 2 and set visited[2] = 1.

SCCS backtrack from node 2 to node 4 and append node 2 to the order.

SCCS backtrack from node 4 to node 1 and append node 4 to the order.

Since there is no unvisited neighbours for node 1, SCCS just append it to the order.

SCCS moves to next unvisited node - node 3.

SCCS moves to node 5 and set visited[5] = 1.

SCCS moves to node 6 and set visited[6] = 1.

SCCS moves to node 7 and set visited[7] = 1.

SCCS backtrack from node 7 to node 6 and append node 7 to the order.

SCCS backtrack from node 6 to node 5 and append node 6 to the order.

SCCS backtrack from node 5 to node 3 and append node 5 to the order.

Since there is no unvisited neighbours for node 3, SCCS just append it to the order.

Now SCCS visit nodes in reversed order on transposed graph.

SCCS starts from node 3, set visited[3] = 1 and add it to current strongly connected component (CSCC).

SCCS moves to node 7, set visited[7] = 1 and add it to CSCC.

SCCS moves to node 6, set visited[6] = 1 and add it to CSCC.

SCCS moves to node 5, set visited[5] = 1 and add it to CSCC.

SCCS repeatedly backtrack from node 5 to node 6, then node 7 and finally node 3 and is done for this strongly connected component.

Then SCCS moves to the next node in reversed order - node 1, set visited[1] = 1 and add it to CSCC.

SCCS moves to node 2, set visited[2] = 1 and add it to CSCC.

SCCS moves to node 4, set visited[4] = 1 and add it to CSCC.

SCCS repeatedly backtrack from node 4 to node 2, then node 1 and is done for this strongly connected component.

Strongly Connected Components Search algorithm is finished.

Code

Python 

                        def strongly_connected_components_search(
                            graph: Dict[int, List[int]],
                        ) -> List[List[int]]:
                            n = len(graph)
                            visited = [False] * n

                            condensation_order = []

                            def compute_order(node: int):
                                nonlocal visited, condensation_order
                                visited[node] = True
                                for neighbour in graph[node]:
                                    if False == visited[neighbour]:
                                        compute_order(neighbour)
                                condensation_order.append(node)

                            for i in range(n):
                                if False == visited[i]:
                                    compute_order(i)

                            transposed_graph: Dict[int, List[int]] = {i: [] for i in range(n)}
                            for i in range(n):
                                for j in graph[i]:
                                    transposed_graph[j].append(i)

                            visited = [False] * n

                            strongly_connected_component = []

                            def compute_strongly_connected_component(node: int):
                                nonlocal visited, transposed_graph, strongly_connected_component
                                visited[node] = True
                                strongly_connected_component.append(node)
                                for neighbour in transposed_graph[node]:
                                    if False == visited[neighbour]:
                                        compute_strongly_connected_component(neighbour)

                            result: List[List[int]] = []
                            for i in range(n - 1, -1, -1):
                                node = condensation_order[i]
                                if False == visited[node]:
                                    compute_strongly_connected_component(node)
                                    result.append(strongly_connected_component[:])
                                    strongly_connected_component.clear()

                            return result
C++