pygraphs.kosaraju_components#

kosaraju_components(graph, *, _skip_check=False)[source]#

Compute the strongly connected components (SCC) of a directed graph using the Kosaraju algorithm (based on DFS).

A strongly connected component is a maximal set of vertices such that every vertex is reachable from every other vertex in both directions.

In other words, for any vertices u and v in the same component: there exists a path from u to v and a path from v to u.

Parameters:

  • graph (Graph) – An instance of the Graph class representing a directed graph on which strongly connected components will be computed.

  • _skip_check (bool)

Returns:

A list of strongly connected components. Each component is represented as a list of vertex indices. The order of components is not guaranteed.

If the graph is empty, an empty list is returned.

Return type:

List[List[int]]

Notes

Kosaraju’s algorithm computes strongly connected components using two DFS traversals.

It proceeds in three main steps:

  • a first DFS to compute the vertices in order of finishing time,

  • reversal of all edges in the graph,

  • a second DFS on the reversed graph following the reverse finishing order.

During the second pass, each DFS tree identifies a strongly connected component.

A strongly connected component is a maximal set of vertices such that every vertex is reachable from every other vertex in both directions.

In other words, for any vertices u and v in the same component: there exists a path from u to v and a path from v to u.

Kosaraju’s algorithm maintains:

  • a list of vertices ordered by decreasing finishing time from the first DFS,

  • a reversed version of the input graph,

  • a visited set to avoid revisiting nodes during the second DFS.

Each time a new DFS is started in the second pass, all reachable vertices in the reversed graph form a complete strongly connected component.

Complexity:

  • Time complexity: \(O(V + E)\)

  • Space complexity: \(O(V)\)

Unlike Tarjan’s algorithm, Kosaraju requires building the reversed graph and performing two separate DFS traversals, but is often simpler to implement and reason about.

See also

pygraphs.dfs()

Core depth-first search traversal.

Examples

Create a simple directed graph of 7 vertices and compute its strongly connected components.

../../_images/graph_directed.png

Directed graph with 7 vertices. Strongly connected components are: {0, 1, 2}, {3, 4}, {5}, {6}.#

1from pygraphs import dfs_kosaraju, Graph
2
3graph = [[1, 2], [0, 2], [1, 0, 3], [4], [3], [6], []]
4graph = Graph.from_adjacency(graph)
5
6components = dfs_kosaraju(graph)
7print(components)

[[0, 1, 2], [3, 4], [5], [6]]