DEV Community

Cover image for Understanding Tarjan’s Algorithm with Visual Examples
Muhammad Taaha Tariq
Muhammad Taaha Tariq

Posted on • Edited on

Understanding Tarjan’s Algorithm with Visual Examples

#algorithms #computerscience #datastructures #programming

Tarjan's algorithm

Muhammad Taaha Tariq

August 2025

Introduction

Graphs are widely used to model real-world systems such as social networks, communication channels, and dependency structures. In directed graphs, cycles are particularly significant, and analyzing them through Strongly Connected Components (SCCs) provides valuable insight into the graph’s structure.

An SCC is defined as a subset of nodes in which every node is reachable from every other node within the same subset. Identifying these components is important in applications like deadlock detection, dependency analysis, and compiler optimization.

Among the most efficient methods for this task is Tarjan’s Algorithm, which leverages Depth-First Search (DFS) along with discovery and low-link values to compute SCCs in linear time. This article explains the concept of SCCs and illustrates Tarjan’s Algorithm step by step with examples.

But before diving right into the algorithm, here's a brief recap of the associated concepts.

Graph

A graph is a mathematical structure, particularly in graph theory, consisting of vertices(nodes) and edges that interlink the nodes with each other. In the context of computer science, however, a graph refers to a data structure whose vertices represent some kind of entity(it may be a network node or some data) that is linked to other vertices using connection links(edges).

It consists of two sets:

V=v  ∣  set of all vertices\mathbf{V} = { v \;|\; \text{set of all vertices} }

E=e  ∣  set of all the edges\mathbf{E} = { e \; |\; \text{set of all the edges}}

Pictorially, it is depicted as circles connected by lines or arrows for different types of graphs.

Undirected Graph

Two nodes are said to be adjacent if they have an interconnecting edge between them. Adjacency simplifies the concept of interconnection by considering only the nodes adjacent to a given node. Given the above graph, we see that the adjacency list of node A is:

[B,  C][\text{B}, \; \text{C}]

Furthermore, edges can be directed or undirected. A directed edge represents a unidirectional connection between the two nodes wherein we can only move from one node to the other but not in the other direction, and is commonly depicted with a pointed arrow.

directed edge

An undirected edge, on the other hand, represents a bidirectional connection between the two nodes.

Based on the nature of the edges between the nodes of a graph, there are two types of graphs that are commonly used in computer science: undirected graphs and directed graphs.

Strongly Connected Components

A strongly connected component of a directed graph is a maximal subgraph where each vertex(node) is mutually reachable.

A subgraph refers to a portion of a graph, or more formally, a subset of the vertex set. The maximality condition refers to the fact that the subgraph cannot be extended while maintaining mutual reachability.

The strongly connected components, therefore, partition the graph into disjoint subgraphs.

SCCs

Depth-first Search

Depth-first Search is a traversal algorithm that traverses the graph recursively. The important thing to note is that it traverses the graph as a spanning tree.

A spanning tree of a connected graph connects all the nodes of the graph using the minimum number of edges and contains no cycles. Since there are many spanning trees of a graph, the DFS traversal order is not unique.

Considering the graph in figure 1 and starting at A, one possible spanning tree is:

Spanning tree

The DFS traversal that produces this spanning tree is as follows:

  • Start at A.
  • Recursively, call the routine for B. Then, for D and finally for C.
  • Then, we backtrack to A.

But, during the traversal, we need to keep track of already visited nodes to prevent indefinite behavior because of cycles, which can be achieved by using an array.

Some additional concepts

DFS spanning trees have two kinds of edges: tree edges and back edges.

  • Back edges relate a tree node to its ancestor in the traversal order.
  • Tree edges take us from the parent node to its children.

However, the two most important concepts responsible for this algorithm's efficiency are discovery time and low values.

  • Discovery time is the time it takes for the DFS to reach a node.
  • Low values indicate the smallest discovery time reachable from a node. Low values less than a node's discovery time indicate a back edge (a cycle).

Tarjan's algorithm for directed graphs

Tarjan's algorithm is used to find the Strongly Connected Components(SCCs) of a directed graph.

Algorithm

  • Start at any vertex and assign it a discovery time and a low value of 0.
  • Iterate over its adjacent nodes, and we push them onto a stack to keep track of the order in which they were traversed, which is essential to correctly updating the low values and identifying potential SSCs, and for the unvisited nodes, recursively call DFS.

  • For each subsequent node:

    • If the adjacent node has already been visited (back edge), update:
      low[u]=min⁡(low[u],  disc[v])low[u] = \min(low[u], \; disc[v])
    • If the adjacent node has not been visited yet, call DFS and on backtracking, update:
      low[u]=min⁡(low[u],  low[v])low[u] = \min(low[u], \; low[v])

  • SCC identification: If

    low[u]=disc[u]low[u] = disc[u]

    , then u is the root of an SCC. Pop nodes from the stack until u is popped.

Explanation

Tarjan's algorithm for undirected graphs

A slightly modified version of Tarjan's algorithm is used for undirected graphs to find the bridges and articulation points.

Algorithm

  • Start at any vertex and assign it a discovery time and a low value of 0.
  • Iterate over adjacent nodes, calling DFS with the parent node.

  • For each node:

    • If the adjacent node is the parent, skip.
    • If already visited, update:
      low[u]=min⁡(low[u],  disc[v])low[u] = \min(low[u], \; disc[v])
    • Otherwise, DFS recursively and backtrack update:
      low[u]=min⁡(low[u],  low[v])low[u] = \min(low[u], \; low[v])

  • Bridge check: If

    low[u]>disc[v]low[u] > disc[v]

    , then (u, v) is a bridge.

  • Articulation point check: If

    disc[u]<=low[v]disc[u] <= low[v]

    , then u is an articulation point (except the root).

Note: In undirected graphs, we skip the parent node because otherwise every parent-child edge looks like a bridge.

Conclusion

The importance of graphs for computer networks and, in general, for computers cannot be overemphasized, and as such, graphs arise in many different applications, and with them arises the need to efficiently work with them on a large scale something that is supplemented by the development of new and more efficient algorithms, one example of such an algorithm is the Tarjan's algorithm which partitions the graph in linear time complexity O(V + E).

References

  1. R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160, 1972. doi:10.1137/0201010.
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009.
  3. GeeksforGeeks. Tarjan’s Algorithm to Find Strongly Connected Components. Accessed: Aug 2025.

Top comments (0)