Tarjan's Algorithm
Description
Tarjan's algorithm is a graph theory algorithm for finding strongly connected components of a directed graph. It runs in linear time and uses a single depth-first search, making it more efficient than Kosaraju's algorithm in practice. The algorithm is based on finding the lowest reachable vertex ID in each connected component.
History
The algorithm was developed by Robert Tarjan in 1972. At the time, Tarjan was a graduate student at Stanford University. This algorithm was one of his many contributions to computer science, for which he later won the Turing Award in 1986. The algorithm showcases an elegant use of depth-first search and demonstrates how complex graph problems can be solved efficiently with the right approach.
How It Works
Tarjan's algorithm uses a depth-first search (DFS) approach with additional tracking of vertices:
-
Discovery Time and Low-Link Values:
- Each vertex is assigned a discovery time when first visited
- A low-link value tracks the lowest discovery time reachable
-
Stack Management:
- Vertices are pushed onto a stack as they're visited
- A vertex remains on the stack until its entire SCC is found
-
Component Identification:
- When a vertex's low-link equals its discovery time, it's a root
- Pop vertices from stack until root is reached to form an SCC
Visualization
Current Step
Click Start to begin
Stack
Empty
Components Found
0
Implementation
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
self.time = 0
def add_edge(self, u, v):
self.graph[u].append(v)
def tarjan_util(self, u, low, disc, stackMember, st, sccs):
disc[u] = self.time
low[u] = self.time
self.time += 1
stackMember[u] = True
st.append(u)
# Go through all vertices adjacent to this
for v in self.graph[u]:
# If v is not visited yet, then recur for it
if disc[v] == -1:
self.tarjan_util(v, low, disc, stackMember, st, sccs)
# Check if the subtree rooted with v has a connection to
# one of the ancestors of u
low[u] = min(low[u], low[v])
elif stackMember[v] == True:
# Update low value of 'u' only if 'v' is still in stack
low[u] = min(low[u], disc[v])
# head node found, pop the stack and create an SCC
w = -1 # To store stack extracted vertices
if low[u] == disc[u]:
scc = []
while w != u:
w = st.pop()
scc.append(w)
stackMember[w] = False
sccs.append(scc)
def tarjan(self):
# Mark all the vertices as not visited
# and Initialize parent and visited arrays
disc = [-1] * self.V
low = [-1] * self.V
stackMember = [False] * self.V
st = []
sccs = []
# Call the recursive helper function
# to find articulation points
# in DFS tree rooted with vertex 'i'
for i in range(self.V):
if disc[i] == -1:
self.tarjan_util(i, low, disc, stackMember, st, sccs)
return sccs
# Example usage
if __name__ == "__main__":
g = Graph(5)
g.add_edge(1, 0)
g.add_edge(0, 2)
g.add_edge(2, 1)
g.add_edge(0, 3)
g.add_edge(3, 4)
print("Strongly Connected Components:")
sccs = g.tarjan()
for i, scc in enumerate(sccs):
print(f"Component {i + 1}: {scc}")
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
int V;
vector<vector<int>> adj;
int time;
void tarjanUtil(int u, vector<int>& disc, vector<int>& low,
stack<int>& st, vector<bool>& stackMember,
vector<vector<int>>& sccs) {
disc[u] = low[u] = ++time;
st.push(u);
stackMember[u] = true;
// Go through all vertices adjacent to this
for(int v : adj[u]) {
// If v is not visited yet, then recur for it
if(disc[v] == -1) {
tarjanUtil(v, disc, low, st, stackMember, sccs);
low[u] = min(low[u], low[v]);
}
// Update low value of u only if v is still in stack
else if(stackMember[v])
low[u] = min(low[u], disc[v]);
}
// head node found, pop the stack and create an SCC
if(low[u] == disc[u]) {
vector<int> scc;
int w = 0;
while(w != u) {
w = st.top();
st.pop();
scc.push_back(w);
stackMember[w] = false;
}
sccs.push_back(scc);
}
}
public:
Graph(int vertices) : V(vertices), time(0) {
adj.resize(V);
}
void addEdge(int v, int w) {
adj[v].push_back(w);
}
vector<vector<int>> tarjan() {
vector<int> disc(V, -1);
vector<int> low(V, -1);
vector<bool> stackMember(V, false);
stack<int> st;
vector<vector<int>> sccs;
for(int i = 0; i < V; i++)
if(disc[i] == -1)
tarjanUtil(i, disc, low, st, stackMember, sccs);
return sccs;
}
};
int main() {
Graph g(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(3, 4);
cout << "Strongly Connected Components:\n";
auto sccs = g.tarjan();
for(int i = 0; i < sccs.size(); i++) {
cout << "Component " << i+1 << ": ";
for(int v : sccs[i])
cout << v << " ";
cout << endl;
}
return 0;
}
public class Graph
{
private int V;
private List<List<int>> adj;
private int time;
public Graph(int vertices)
{
V = vertices;
time = 0;
adj = new List<List<int>>();
for (int i = 0; i < V; i++)
{
adj.Add(new List<int>());
}
}
public void AddEdge(int v, int w)
{
adj[v].Add(w);
}
private void TarjanUtil(int u, int[] disc, int[] low, Stack<int> st,
bool[] stackMember, List<List<int>> sccs)
{
disc[u] = low[u] = ++time;
st.Push(u);
stackMember[u] = true;
foreach (int v in adj[u])
{
if (disc[v] == -1)
{
TarjanUtil(v, disc, low, st, stackMember, sccs);
low[u] = Math.Min(low[u], low[v]);
}
else if (stackMember[v])
{
low[u] = Math.Min(low[u], disc[v]);
}
}
if (low[u] == disc[u])
{
List<int> scc = new List<int>();
int w;
do
{
w = st.Pop();
stackMember[w] = false;
scc.Add(w);
} while (w != u);
sccs.Add(scc);
}
}
public List<List<int>> Tarjan()
{
int[] disc = new int[V];
int[] low = new int[V];
bool[] stackMember = new bool[V];
Stack<int> st = new Stack<int>();
List<List<int>> sccs = new List<List<int>>();
for (int i = 0; i < V; i++)
{
disc[i] = -1;
low[i] = -1;
}
for (int i = 0; i < V; i++)
{
if (disc[i] == -1)
{
TarjanUtil(i, disc, low, st, stackMember, sccs);
}
}
return sccs;
}
}
public class Program
{
public static void Main()
{
Graph g = new Graph(5);
g.AddEdge(1, 0);
g.AddEdge(0, 2);
g.AddEdge(2, 1);
g.AddEdge(0, 3);
g.AddEdge(3, 4);
Console.WriteLine("Strongly Connected Components:");
var sccs = g.Tarjan();
for (int i = 0; i < sccs.Count; i++)
{
Console.Write($"Component {i + 1}: ");
Console.WriteLine(string.Join(" ", sccs[i]));
}
}
}
Complexity Analysis
Time Complexity
The time complexity of Tarjan's algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This can be broken down into:
-
DFS: O(V + E)
- Each vertex is visited exactly once: O(V)
- Each edge is traversed exactly once: O(E)
-
Stack Operations: O(V)
- Each vertex is pushed and popped exactly once
Space Complexity
The space complexity is O(V), which includes:
-
Arrays disc[] and low[]: O(V)
- Store discovery times and low-link values for each vertex
-
Stack: O(V)
- Stores vertices during processing
-
Array stackMember[]: O(V)
- Tracks which vertices are in the stack
-
Output Storage: O(V)
- For storing the strongly connected components
Advantages and Disadvantages
Advantages
- Linear time complexity O(V + E)
- Requires only one graph traversal
- More space-efficient than Kosaraju's algorithm
- No need to construct the transpose graph
Disadvantages
- More complex implementation
- Harder to understand conceptually
- Requires maintaining more state during traversal
- Less intuitive than other SCC algorithms