pygraphs.tarjan_components#

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

Compute the strongly connected components (SCC) of a directed graph using Tarjan’s algorithm.

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, optional (default: False)) – If True, skip input validation checks for performance reasons.

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

Tarjan’s algorithm computes strongly connected components in a single DFS traversal.

It maintains:

  • an index counter assigning a unique discovery time to each node,

  • a low-link value representing the smallest index reachable from a node,

  • a stack of active nodes currently in the DFS recursion tree.

A node is identified as the root of a strongly connected component when: lowlink[node] == index[node].

At this point, all nodes on the stack up to that node form a complete SCC.

Complexity:

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

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

Unlike Kosaraju’s algorithm, Tarjan does not require reversing the graph or performing multiple DFS passes.

See also

pygraphs.dfs()

Core depth-first search traversal.

pygraphs.kosaraju_components()

Alternative SCC algorithm based on two DFS passes.

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 tarjan_components, Graph
2
3graph = [[1, 2], [0, 2], [1, 0, 3], [4], [3], [6], []]
4graph = Graph.from_adjacency(graph)
5
6components = tarjan_components(graph)
7print(components)

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