一、Tarjan算法简介 Tarjan算法是由Robert Tarjan发明的一种基于DFS的图论算法，他可以用来求解有向图的强联通分量或者求解无向图的中的割点和桥等，可以说是图论算法中的基本算法之一。本文将以求解有向图的强联通分量来介绍Tarjan算法。 二、有向图的强联通 有向图的两个结点可以相互到达，他们便在一个强联通分量内，如图所示：
其中{1,2,3,5}四个结点可以相互到达，故他们为一个强联通分量，而{4}，{6}分别为一个强联通分量。
二、Tarjan算法思路 Tarjan算法实现需要两个数组，dfn数组和low数组：dfn数组：用来记录每个节点在dfs遍历树中的顺序，即判断该节点实在dfs中是第几个节点被遍历到的。low数组：记录该节点能够到达的未被找到强联通分量的结点的dfn值，其中初始化时和dfn值相等，并且最后dfs值相同的结点在一个强联通分量中。trace：是一个栈，每访问一个节点便入栈算法步骤：其中橙色节点表示当前访问的结点，灰色节点表示已经找到强联通分量的结点，绿色节点表示当前 节点能够到达的low值最小的节点。
访问节点1，初始时将dfn[1]=low[1]=1，将该节点加入栈中
访问节点2，dfn[2]=low[2]=2，将该节点加入栈
访问节点4，dfn[4]=low[4]=3，将该节点加入栈
访问节点6，dfn[6]=low[6]=4，此时6节点没有其他的邻接节点，故判断dfn[6]==low[6]
成立，则该节点为一个强联通分量的根。将6出栈并且加到结果中。
将6出栈后，会将其low值设为所有dfn值中的最大值+1，此时相当于对该节点已经寻找强联通分量完毕做一个记号，也可以采用一个新的数组来标记，效果是一样的。并回溯到4节点。
4节点的所有孩子结点都被访问完毕，并且dfn[4]==low[4]成立，此时相当于又找到一个强联通分量的根节点。
回退到2节点。由于4节点的low值大节点的low值，故不用更新（每次回退会检查更新），此时2节点的邻接节点5结点未被访问，便访问5结点，dfn[5]=low[5]=5；
5节点的所有邻接节点都被访问，但是1节点还在栈中（没有找到1节点相关的强联通分量），并且low[1]等于1,low[5]>low[1],便将low[5]更新为1.
然后回退到2结点，并且更新low值为5节点的low值（每次回退会检查更新）：
回退到1节点，并发现1结点的邻接节点3节点未被访问,访问3节点，并且dfs[3]=low[3]=6。
3结点的所有邻接节点都被访问过，更新其low值为所有邻接节点中的最小的low值
回退到1结点，并且1结点的所有邻接节点都被访问，并且low[1]==dfn[1],表示又找到一个联通分量。
至此，所有节点访问完毕。
总结：
1、每个节点初始化时dfn值和low值都是一样的并且都为++count。
2、当访问该节点v的邻接节点w时，如果没被访问过，便dfs递归访问w，如果w已经被访问过便更新low[v]=min(low[v],low[w])。
3、每次节点w访问完毕，回退到递归树的父节点v的时候，会检查更新其low[v]=min(low[v],low[w])
4、当该节点v的所有邻接节点都访问完毕时，并且low[v]==dfn[v]时，v就是一个强联通分量的根节点。
三、Tarjan算法代码（递归） public class Tarjan { private DirectedGraph graph; private int dfn[]; private int low[]; private int cnt; private Stack<Integer> trace;//存储dfs递归树的顺序 private List<HashSet> cctargan;//存储所有强联通分量 public Tarjan(DirectedGraph graph) { this.graph = graph; dfn = new int[graph.V() + 1]; low = new int[graph.V() + 1]; trace = new Stack<>(); cctargan = new ArrayList<>(); for (int i = 1; i <= graph.V(); i++) { if (dfn[i] == 0) {//表示i节点没有被访问 dfs(i); } } } private void dfs(int v) { cnt++; dfn[v] = cnt; trace.push(v); low[v] = dfn[v]; for (int w : graph.toVertex(v)) { if (dfn[w] == 0) {//w未被访问 dfs(w); low[v] = Math.min(low[w], low[v]);//每个v的邻接节点找完后都会更新low[v] } else {//已经被访问 low[v] = Math.min(low[v], low[w]); } } //判断时否为一个联通分量的根 if (low[v] == dfn[v]) { int cur; HashSet<Integer> set = new HashSet<>(); do { cur = trace.pop(); set.add(cur); low[v] = Integer.MAX_VALUE; } while (cur != v); cctargan.add(set); } }} 四、Tarjan算法代码（非递归）
当测试用例很大的时候，由于递归深度太深会抛出栈溢出的错误，此时可以用人工栈的方式来实现Tarjan的非递归写法。本程序并没有完全按照系统栈的调用过程进行改进。
由tarjan的算法思想可以知道主要分成2个部分。
1、递归访问。在递归实现中，当结点v的邻接节点w没被访问过，便递归访问，如果w访问过，便更新low[v]=min(low[v],low[w]),此时的过程很像dfs的非递归写法，即将所有的结点加入栈中，表示他已经被dfs遍历过，注意，此时被遍历过并不意味着后面就不会再次访问该节点，因为还可能回溯回来再次访问该节点，所有此时用peek()方法查看该节点，而不用pop()方法。
2、当该节点的所有邻居节点都访问完毕过后，首先应该判断该节点是否有（low[v]==dfn[v]），来判断该节点是否是强联通分量的根节点。并且，还需要回溯到其dfs递归树的父亲结点，去更新父亲结点的low值，所以这里需要parent数组存储每个节点的上一个节点，方便更新。
,
public class Tarjannr { private DirectedGraph graph; private int dfn[]; private int low[]; private Stack<Integer> st;//模拟系统栈 private Stack<Integer> trace;//存储dfs遍历结点顺序 private int cnt; private List<HashSet> cctargan;//存储所有强联通分量 public Tarjannr(DirectedGraph graph) { this.graph = graph; dfn = new int[graph.V() + 1]; low = new int[graph.V() + 1]; st = new Stack<>(); trace = new Stack<>(); cctargan = new ArrayList<>(); for (int v : graph.getVertex()) { if (dfn[v] == 0) { dfsnr(v); } } } private void dfsnr(int v) { st.push(v); int parent[] = new int[graph.V() + 1];//用来存储每个节点在dfs递归树中的父亲结点 parent[v] = v; while (!st.isEmpty()) { v = st.peek(); if (dfn[v] == 0) { trace.add(v); dfn[v] = low[v] = ++cnt; } boolean flag = false; for (int w : graph.toVertex(v)) { parent[w] = v;//w的父节点为v if (dfn[w] == 0) { flag = true; st.push(w); } else {//已经被访问 low[v] = Math.min(low[w], low[v]); } } //表示该节点的孩子结点已经全部被访问了，应该更新其父亲结点的low值，并且判断该节点是 //否是强联通分量的根节点 if (!flag) { v = st.pop(); low[parent[v]] = Math.min(low[parent[v]], low[v]); if (low[v] == dfn[v]) { int cur; HashSet<Integer> set = new HashSet<>(); do { cur = trace.pop(); set.add(cur); low[v] = Integer.MAX_VALUE; } while (cur != v); cctargan.add(set); } } //所有孩子结点遍历完会更新自己的值返回回去更新父节点的值 } }} 五、总结
Tarjan算法的非递归实现从逻辑上很难理解，如有错误，望请大家指正。