tarjan算法是一个求取有向图的所有强连通分量的算法，它是以算法提出者Robert Tarjan的名字来命名的。提出此算法的Robert Tarjan是普林斯顿大学的教授，同时他也是1986年的图灵奖获得者（图灵奖是计算机领域的最高荣誉，和物理、化学领域的诺贝尔奖是一个层次的奖项）。
在详细讲述该算法之前，我们需要明确几个概念（注意该算法的研究对象是有向图，无向图没有强连通等概念）。
1. 强连通
如果两个顶点可以互相通达，则称这两个顶点强连通。
2. 强连通图
如果有向图G中的任意两个顶点都是强连通的，那么我们称该有向图G是强连通图。
3. 强连通分量
非强连通图的极大强连通子图称为强连通分量。
例如Graph 1就是一个强连通图，Graph 2 不是强连通图，因为4节点不存在到1、2和3的路径。
下面介绍该算法的处理流程：
1. 首先定义两个数组dfn和low，其中dfn用于记录dfs（深度优先搜索）时，当前节点u的访问时间戳，这里用计数器实现。low用于记录以当前节点u作为根节点能达到的最短时间戳，因为如果出现回边，此时的low值就可能会变小。
2. 初始化时，令节点u的dfn和low值为当前的时间戳count。
3. 如果当前节点u有相连的节点v，此时分为以下几种处理情况。
- v节点未访问过，此时直接递归处理v。递归返回时low[u]=min{low[u],low[v]}。
- v节点已访问过且v已和其它节点构成了一个连通分量，即v不在栈中，此时(u,v)为横叉边，不做任何处理。
- v节点已访问过且v在栈中，此时(u,v)是回边，low[u]=min{low[u],dfn[v]}。注意v节点由于仍在栈中，所以其low[v]的最终值还不确定，当然low[v]总是小于等于dfn[v]的，因此二者都行。
4. 当u节点的所有连接边处理完毕时，low[u]的值也就确定了。此时比较dfn[u]和low[u]的值，若二者相同，则说明栈中从该节点往上的所有节点构成一个强连通分量，将其弹出即可。要理解这个判定规则的原理，需要明确dfn和low的定义，这里dfn[u]表示节点u第一次访问时的时间戳，low[u]是u的子节点能达到的最小时间戳，若u无子节点，则low[u]等于dfn[u]，即u节点自身构成一个强连通分量。
5. 需要注意的是当我们处理完一个强连通分量时，有可能需要改变搜索的起点，因此我们可以在外围添加一个循环，若某个节点未访问过，则调用1-4步骤进行处理。
以下是该算法的伪代码描述。
tarjan(u)
{
dfn[u]=low[u]=++count // 为节点u设定时间戳dfn和low初值
stack.push(u) // 将节点u压入栈中
for each (u, v) in E // 枚举u的每一条出边
if (v is not visited) // 如果节点v未被访问过
tarjan(v) // 递归向下处理
low[u] = min(low[u], low[v])
else if (v in S) // 如果节点v还在栈内
low[u] = min(low[u], dfn[v])
if (dfn[u] == low[u]) // 如果节点u是强连通分量的根
repeat
v = stack.pop // 将v出栈，v为该强连通分量中一个顶点
print v
until (u== v)
}
接下来是对算法流程的演示。
从节点1开始dfs，把遍历到的节点加入栈中。搜索到节点u=6时，dfn[6]=low[6]，此时找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。
返回节点5，发现dfn[5]=low[5]，退栈后{5}为一个强连通分量。
返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有回边，节点1还在栈中，所以low[4]=dfn[1]=1。节点6已经出栈，(4,6)是横叉边，返回3，所以low[3]=low[4]=1。
继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以low[2]=dfn[4]=5。返回1后，low[1]=1，即dfn[1]=low[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。注意，栈顶在下部。
至此，算法结束。经过该算法，求出了图中三个强连通分量{1,3,4,2},{5},{6}。注意在实现时，dfs顺序可能会变化，所以要灵活看待。
可以发现，运行tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(n+e)。其中n为有向图G的顶点数量，e为G的边数。
下面给出该算法在java语言下的实现。
import java.util.Stack;
//采用javabean封装
class Edge //边节点
{
private int value; //边(u,v)中的v值
private Edge next; //采用邻接链表存储图
public Edge(int value, Edge next) {
super();
this.value = value;
this.next = next;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Edge getNext() {
return next;
}
public void setNext(Edge next) {
this.next = next;
}
}
class DingDian //顶点节点
{
private int value; //边(u,v)中的u值
private Edge next; //采用邻接链表存储图
public DingDian(int value, Edge next) {
super();
this.value = value;
this.next = next;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Edge getNext() {
return next;
}
public void setNext(Edge next) {
this.next = next;
}
}
public class Main {
static DingDian[] head;
static int[] visited; //记录顶点是否访问过，0：未访问 1：访问过且在栈中 2：访问过且已出栈
static int[] dfn; //记录深搜时的时间戳
static int[] low; //记录节点能达到的最小时间戳
static Stack<Integer> stack; //保存节点编号，用于生成强连通分量
static int count = ; //时间戳计数器
public static void tarjan()
{
for (int i = ; i < visited.length; i++) { //外围控制（引入原因：有可能需要改变搜索起点）
if(visited[i]==)
tarjanProc(head[i]);
}
}
public static void tarjanProc(DingDian uD)
{
if(uD==null)
return;
int u = uD.getValue();
dfn[u] = low[u] = count++; //初始化dfn和low值
visited[u] = ; //节点u设置为已访问过
stack.push(u); //节点u入栈
Edge edge = uD.getNext();
while(edge != null) //处理u的所有出边
{
int v = edge.getValue();
if(visited[v] == )
{
tarjanProc(head[v]); //v节点未访问过，则递归处理
low[u] = Math.min(low[u], low[v]);
}
else if(visited[v]==) //v节点访问过，且在栈中
low[u] = Math.min(low[u], dfn[v]);
edge = edge.getNext();
}
if(dfn[u] == low[u]) //强连通分量判定准则
{
while(!stack.isEmpty())
{
int temp = stack.pop();
visited[temp] = ; //节点temp已访问过，且已出栈
if(temp==u)
{
System.out.println(temp);
return;
}
else
System.out.print(temp+" ");
}
}
}
public static void main(String[] args) {
int n =;
head = new DingDian[n+]; //下标从1开始
visited = new int[n+];
dfn = new int[n+];
low = new int[n+];
stack = new Stack<Integer>();
head[] = new DingDian(,null);
head[].setNext(new Edge(,null));
head[].getNext().setNext(new Edge(,null));
head[] = new DingDian(,null);
head[].setNext(new Edge(,null));
head[] = new DingDian(,null);
head[].setNext(new Edge(,null));
head[].getNext().setNext(new Edge(,null));
head[] = new DingDian(,null);
head[].setNext(new Edge(,null));
head[].getNext().setNext(new Edge(,null));
head[] = new DingDian(,null);
head[].setNext(new Edge(,null));
head[] = new DingDian(,null);
tarjan();
}
}