【图论】Tarjan算法详解
在学习Tarjan算法之前，要先了解强连通的相关知识点！
- 强连通： 在一个有向图G里，如果有两个点（a、b）可以相互到达，我们就叫这两个顶点（a，b）为强连通。
- 强连通图： 如果在一个有向图G中，每两个点都强连通（可以相互到达），我们就叫这个图为强连通图。
- 强连通分量（SCC）： 在一个有向图G中，有一个子图，这个子图每2个点都满足强连通，我们就叫这个子图叫做 强连通分量，孤立的点也是一个强连通分量。
例：下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。
Tarjan算法
Tarjan算法是一种用来求解有向图强连通分量的线性时间的算法。可以找强连通分量，也可以找缩点、割点等。
算法思路：
Tarjan算法是基于DFS的，每个强连通分量为搜索树的一棵子树，搜索时把当前搜索树中未处理的节点加入一个栈，回溯时判断栈顶到栈中节点是否为强连通分量。
为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进行。在DFS时每个点都需要记录两个数组：
- DFN[u]： 代表u点DFS到的时间，即时间戳，简单来说就是 第几个被搜索到的。可知在同一个DFS树的子树中，DFN[u] 越小，则其越浅。
- Low[u]： 代表在DFS树中，u或u的子树 能够追溯到的最早的栈中节点的 时间戳。
算法过程：
（1）数组的初始化：对图进行深度优先搜索（DFS），在搜索过程中用 DFN 记录搜索的顺序。当首次搜索到点u 时，DFN 与 Low 数组的值都为 到该点的时间。
（2）堆栈：采用栈（记录已经搜索过的但是未删除的点）,每搜索到一个点，将它压入栈顶。如果这个点有 出度 就继续往下找，直到找到底。
（3）每次返回时都将子节点与该节点的Low值进行比较，谁小就取谁，保证最小的子树根。
- 当点u 有与点u’ 相连时，如果此时（时间为DFN[u]时）u’不在栈中，u的 Low 值为两点的 Low值 中较小的一个。
- 当点u 有与点u’ 相连时，如果此时（时间为DFN[u]时）u’在栈中，u的 Low 值为 u的 Low值 和u’的 DFN值 中较小的一个
（4）每当搜索到一个点经过以上操作后（也就是子树已经全部遍历）的 Low值等于DFN值（ DFN[u] == Low[u]），则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。
原因：u点在DFS树中，子节点（后代）不能找到更浅的点，那么 u点及其后代构成一个SCC（强连通分量）。且 u点 是这个强连通分量的根节点（因为这个Low[] 值是这个强连通分量里最小的。）
（5）继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。
伪代码：
tarjan(u){DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值Stack.push(u) // 将节点u压入栈中for each (u, v) in E // 枚举每一条边if (v is not visted) // 如果节点v未被访问过tarjan(v) // 继续向下找Low[u] = min(Low[u], Low[v]) //更新这个点能指出去的最浅的时间戳else if (v in S) // 如果节点u还在栈内Low[u] = min(Low[u], DFN[v])if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根do{v = S.pop // 将v退栈，为该强连通分量中一个顶点}while(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]=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树边，所以Low[3]=Low[4]=1。
- 继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以Low[2]=DFN[4]=5。返回1后，发现DFN[1]=Low[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。
- 至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。
- 可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(V+E)。
还是没能理解？那就再来一个例子演示
- 首先a、b、c、d依次入栈：
直到e不能再往下搜索，此时判断 dfn[4] == low[4]，因此e是一个强连通分量，并从栈中弹出。
- 然后节点d入栈：
接下来 节点d 指向节点b，因此把节点d的 low值更新为2。
- 然后开始回溯，发现节点d：（5,2）不等，节点c：（3,2）不等，直到发现节点b：（2,2）相等，说明以b为根的子树就是一个强连通分量，同时在栈中弹出。
- 接下来已经回溯到节点a，然后指向节点f，于是f入栈：
- 依次节点g入栈：
- 因为节点g 指向节点a，所以把节点g 的low值更新为1。
- 然后开始回溯，由节点g 回溯到节点f，把f的low值也更新为1，再回溯到a，就得到了最后一个强连通分量。
Code：
import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Stack;public class Tarjan {private int numOfNode; //节点数private List< ArrayList<Integer> > graph; //图private List< ArrayList<Integer> > result; //保存极大强连通图private boolean[] inStack; //表示节点是否在栈内，因为在stack中寻找一个节点不方便。这种方式查找快private Stack<Integer> stack;private int[] dfn;private int[] low;private int time; //time表示在栈中的编号public Tarjan(List< ArrayList<Integer> > graph, int numOfNode){ //带参构造this.graph = graph;this.numOfNode = numOfNode;this.inStack = new boolean[numOfNode];this.stack = new Stack<Integer>(); //栈中元素都为整数dfn = new int[numOfNode];low = new int[numOfNode];Arrays.fill(dfn, -1); //将dfn所有元素都置为-1，其中dfn[i]=-1代表节点i还有没被访问过Arrays.fill(low, -1);result = new ArrayList<ArrayList<Integer>>();}public List< ArrayList<Integer> > run(){for(int i=0;i<numOfNode;i++){if(dfn[i] == -1){tarjan(i);}}return result;}//算法的主要代码public void tarjan(int current){ //代表第几个点在处理，递归的是点dfn[current] = low[current] = time++; //新的点首先初始化inStack[current] = true; //表示在栈里stack.push(current); //进栈for(int i=0; i<graph.get(current).size(); i++){ //搜索相连节点int next = graph.get(current).get(i);if(dfn[next] == -1){ //如果没被访问过（-1代表没有被访问）tarjan(next); //递归调用low[current]=Math.min(low[current], low[next]); //更新所能到的上层节点（涉及到强连通分量子树最小根的事情)}else if(inStack[next]){ //如果在栈中,并且被访问过low[current]=Math.min(low[current], dfn[next]); //到栈中最上端的节点}}if(low[current] == dfn[current]){ //发现是整个强连通分量子树里的最小根ArrayList<Integer> temp = new ArrayList<Integer>();int j = -1;while(current!=j){j = stack.pop(); //出栈，并且输出inStack[j] = false; //修改状态为不在栈中temp.add(j);}result.add(temp);}}public static void main(String[] args) {//创建图int numOfNode = 6;List< ArrayList<Integer> > graph = new ArrayList<ArrayList<Integer>>();for(int i=0; i<numOfNode; i++){graph.add(new ArrayList<Integer>());}graph.get(0).add(1);graph.get(0).add(2);graph.get(1).add(3);graph.get(2).add(3);graph.get(2).add(4);graph.get(3).add(0);graph.get(3).add(5);graph.get(4).add(5);//调用Tarjan算法求极大连通子图Tarjan t = new Tarjan(graph, numOfNode);List< ArrayList<Integer> > result = t.run(); //结果代码//打印结果for(int i=0; i<result.size(); i++){for(int j=0; j<result.get(i).size(); j++){System.out.print(result.get(i).get(j) + " ");}System.out.println();}}}
例题
原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1269
题意： 一个有向图，有 n 个点（n <= 10000）和 m 条边（m <= 100000）。判断整个图是否强连通，如果是，输出 “Yes”，否则，输出“No”。
思路： Kosaraju 算法模板题，直接求整个图是否为强连通分量。
Code：
#include <iostream>#include <vector>#include <cstring>using namespace std;const int N = 100010;dfnvector<int> G[N];int dfn[N],low[N],sccno[N],s[N];int cnt,dfn,top;void dfs(int u) {s[top++] = u;dfn[u] = low[u] = ++dfn;for(int i=0; i<G[u].size(); i++) {int v=G[u][i];if(!dfn[v]){dfs(v);low[u] = min(low[u],low[v]);}else if(!sccno[v])low[u] = min(low[u],dfn[v]);}if(low[u]==dfn[u]){cnt++;while(1){int v = s[--top];sccno[v] = cnt;if(u==v) break;}}}void Tarjan(int n) {cnt = top = dfn = 0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(sccno,0,sizeof(sccno));for(int i=1;i<=n;i++){if(!dfn[i])dfs(i);}}int main() {int n,m,u,v;while(cin>>n>>m && (n || m)) {for(int i=1;i<=n;i++) G[i].clear();for(int i=1;i<=m;i++) {cin>>u>>v;G[u].push_back(v);}Tarjan(n);cnt==1?cout<<"Yes"<<endl:cout<<"No"<<endl;}return 0;}
参考：Tarjan算法
小鱼儿
浅浅的花香味﹌
港控/mmm°
超、凢脫俗
还没有评论，来说两句吧...