【图论】Tarjan算法详解

浅浅的花香味﹌ 2023-07-25 13:00 31阅读 0赞

在学习Tarjan算法之前，要先了解强连通的相关知识点！

*  **强连通：** 在一个有向图G里，如果有两个点（a、b）可以相互到达，我们就叫这两个顶点（a，b）为强连通。
 *  **强连通图：** 如果在一个有向图G中，每两个点都强连通（可以相互到达），我们就叫这个图为强连通图。
 *  **强连通分量（SCC）：** 在一个有向图G中，有一个子图，这个子图每2个点都满足强连通，我们就叫这个子图叫做 强连通分量，孤立的点也是一个强连通分量。

例：下图中，子图\{1,2,3,4\}为一个强连通分量，因为顶点1,2,3,4两两可达。\{5\},\{6\}也分别是两个强连通分量。

![在这里插入图片描述][2020041515420966.png_pic_center]

## 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）继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。  
  
  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center]

**伪代码：**

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\}为一个强连通分量。

![在这里插入图片描述][202004151541344.png_pic_center]

*  返回节点5，发现DFN\[5\]=Low\[5\]，退栈后\{5\}为一个强连通分量。

![在这里插入图片描述][20200415154310566.png_pic_center]

*  返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以Low\[4\]=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树边，所以Low\[3\]=Low\[4\]=1。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 1]

*  继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以Low\[2\]=DFN\[4\]=5。返回1后，发现DFN\[1\]=Low\[1\]，把栈中节点全部取出，组成一个连通分量\{1,3,4,2\}。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 2]

*  至此，算法结束。经过该算法，求出了图中全部的三个强连通分量\{1,3,4,2\},\{5\},\{6\}。
    
      
    
 *  可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(V+E)。

还是没能理解？那就再来一个例子演示

*  首先a、b、c、d依次入栈：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 3]  
  
  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 6]

*  直到e不能再往下搜索，此时判断 dfn\[4\] == low\[4\]，因此e是一个强连通分量，并从栈中弹出。
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 7]

*  然后节点d入栈：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 8]

*  接下来 节点d 指向节点b，因此把节点d的 low值更新为2。
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 9]  
      
    
 *  然后开始回溯，发现节点d：（5,2）不等，节点c：（3,2）不等，直到发现节点b：（2,2）相等，说明以b为根的子树就是一个强连通分量，同时在栈中弹出。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 10]

*  接下来已经回溯到节点a，然后指向节点f，于是f入栈：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 11]

*  依次节点g入栈：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 12]

*  因为节点g 指向节点a，所以把节点g 的low值更新为1。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 13]

*  然后开始回溯，由节点g 回溯到节点f，把f的low值也更新为1，再回溯到a，就得到了最后一个强连通分量。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 14]

**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][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;dfn
    vector<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算法][Tarjan]

[2020041515420966.png_pic_center]: /images/20230528/d28aa08d9d4745eab6de3197bb3c8fd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/9177d29d1acf466594bd40203e99bdc1.png
[202004151541344.png_pic_center]: /images/20230528/b2b0d20803bc46e88f2d1e39d60e7bb0.png
[20200415154310566.png_pic_center]: /images/20230528/624df0aecdea4ff6872f740e738017e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/084ee90936eb400f8cf0375293c6d931.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/3e5f9e03d05b419d8b159b167d4fbf10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230528/0373d2ecb7d642e989d6615f5d8f0083.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230528/39e2b1f37c43446f9b2ce679d1272768.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20230528/ab420d9cbb1445b3bcc3a9781149ac98.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20230528/9793b218789a4f86ac0980af96158ef5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20230528/38511bb072e14243b87fe726faab616a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20230528/163a47b8552c49738742c52d8796d711.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20230528/41ab860d0adf41898ecc42adb1e85fa9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20230528/2b8b8032b2de414cb90dfef4b738b861.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20230528/f82243fcbf1d4509883b187551eef211.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20230528/01f4936639c24f14aee07de8be11ed77.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20230528/628455e1d3c64bf2918246d5dce21e7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20230528/46b6feba73634a48b05d5294b53d723b.png
[http_acm.hdu.edu.cn_showproblem.php_pid_1269]: http://acm.hdu.edu.cn/showproblem.php?pid=1269
[Tarjan]: https://blog.csdn.net/SpringRolls/article/details/101386049?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-6&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-6