求强连通分量tarjan算法讲解

（转）全⽹最!详!细!tarjan算法讲解全⽹最详细tarjan算法讲解，我不敢说别的。

反正其他tarjan算法讲解，我看了半天才看懂。

我写的这个，读完⼀遍，发现原来tarjan这么简单！tarjan算法，⼀个关于图的联通性的神奇算法。

基于DFS（迪法师）算法，深度优先搜索⼀张有向图。

！注意！是有向图。

根据树，堆栈，打标记等种种神（che）奇（dan）⽅法来完成剖析⼀个图的⼯作。

⽽图的联通性，就是任督⼆脉通不通。

的问题。

了解tarjan算法之前你需要知道：强连通，强连通图，强连通分量，解答树（解答树只是⼀种形式。

了解即可）不知道怎么办神奇海螺～：嘟噜噜～！强连通(strongly connected)：在⼀个有向图G⾥，设两个点 a b 发现，由a有⼀条路可以⾛到b，由b⼜有⼀条路可以⾛到a，我们就叫这两个顶点（a，b）强连通。

强连通图：如果在⼀个有向图G中，每两个点都强连通，我们就叫这个图，强连通图。

强连通分量strongly connected components)：在⼀个有向图G中，有⼀个⼦图，这个⼦图每2个点都满⾜强连通，我们就叫这个⼦图叫做强连通分量［分量：：把⼀个向量分解成⼏个⽅向的向量的和，那些⽅向上的向量就叫做该向量（未分解前的向量）的分量］举个简单的栗⼦：⽐如说这个图，在这个图中呢，点1与点2互相都有路径到达对⽅，所以它们强连通.⽽在这个有向图中，点1 2 3组成的这个⼦图，是整个有向图中的强连通分量。

解答树：就是⼀个可以来表达出递归枚举的⽅式的树（图），其实也可以说是递归图。

反正都是⼀个作⽤，⼀个展⽰从“什么都没有做”开始到“所有结求出来”逐步完成的过程。

“过程！”神奇海螺结束tarjan算法，之所以⽤DFS就是因为它将每⼀个强连通分量作为搜索树上的⼀个⼦树。

⽽这个图，就是⼀个完整的搜索树。

为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进⾏。

每个点都有两个参数。

1，DFN［］作为这个点搜索的次序编号（时间戳），简单来说就是第⼏个被搜索到的。

数据结构课设有向图强连通分量求解强连通分量（Strongly Connected Components）是有向图中的一种特殊的连通分量，指的是图中任意两个顶点之间都存在有向路径。

求解有向图的强连通分量可以使用Tarjan算法，该算法基于深度优先搜索（DFS）。

具体步骤如下：1. 初始化一个栈，用于存储已访问的顶点；2. 对于图中的每一个顶点v，如果v未访问，则进行DFS遍历；3. 在DFS遍历中，对于当前访问的顶点v，设置v的索引号和低链接号为当前索引值，并将v入栈；4. 遍历v的所有邻接顶点w，如果w未访问，则进行DFS遍历，并将w的低链接号更新为min(当前顶点的低链接号, w的低链接号)；5. 如果当前顶点v的低链接号等于索引号，则将v出栈，并将v及其出栈的顶点组成一个强连通分量。

示例代码如下：```pythonclass Graph:def __init__(self, vertices):self.V = verticesself.adj = [[] for _ in range(vertices)]self.index = 0self.lowlink = [float("inf")] * verticesself.onStack = [False] * verticesself.stack = []self.scc = []def addEdge(self, u, v):self.adj[u].append(v)def tarjanSCC(self, v):self.index += 1self.lowlink[v] = self.indexself.stack.append(v)self.onStack[v] = Truefor w in self.adj[v]:if self.lowlink[w] == float("inf"):self.tarjanSCC(w)self.lowlink[v] = min(self.lowlink[v], self.lowlink[w]) elif self.onStack[w]:self.lowlink[v] = min(self.lowlink[v], self.lowlink[w]) if self.lowlink[v] == self.index:scc = []w = -1while w != v:w = self.stack.pop()self.onStack[w] = Falsescc.append(w)self.scc.append(scc)def findSCC(self):for v in range(self.V):if self.lowlink[v] == float("inf"): self.tarjanSCC(v)return self.scc```使用示例：```pythong = Graph(5)g.addEdge(1, 0)g.addEdge(0, 2)g.addEdge(2, 1)g.addEdge(0, 3)g.addEdge(3, 4)print("Strongly Connected Components:") scc = g.findSCC()for component in scc:print(component)```输出结果：```Strongly Connected Components:[4][3][0, 2, 1]```以上代码实现了有向图的强连通分量的求解，通过Tarjan算法进行DFS遍历和低链接号的更新，最终得到所有的强连通分量。

天才少女中提到的特拉亨伯格算法
特拉亨伯格算法（Tarjan's Algorithm）是一种用于在有向图或
无向图中寻找强连通分量的算法，由美国计算机科学家罗伯特·特拉亨伯格（Robert Tarjan）于1972年提出。

强连通分量是指在一个有向图中，任意两个顶点之间都存在双向路径的一组顶点。

特拉亨伯格算法将图的所有顶点分成若干个强连通分量，并给出强连通分量的集合。

算法的基本思想是使用深度优先搜索（DFS）遍历图中的顶点，并通过维护一个栈来记录访问的顺序。

在DFS过程中，对每
个被访问的顶点，记录其访问的顺序号和最早的访问顺序号（即DFS的次数）。

当DFS递归回溯到某个顶点时，在回溯的过程中可以判断是
否遇到了新的强连通分量。

如果某个顶点的最早访问顺序号与自身的访问顺序号一致，说明在回溯的过程中没有找到更早的顶点，这表明从当前顶点出发的路径上的所有顶点都属于同一个强连通分量。

特拉亨伯格算法的时间复杂度为O(V+E)，其中V是顶点数，
E是边数。

在实际应用中，特拉亨伯格算法常被用于解决图相
关问题，如求解有向图的强连通分量、求解有向无环图的拓扑排序等。

Tarjan算法Tarjan算法Tarjan求强连通分量概念：如果两个顶点互相可达，则它们是强连通的。

如果⼀幅有向图中任意两个顶点都是强连通的，则这幅有向图也是强连通的。

强连通分量就是图中具有连通性的⼀个最⼤⼦集，⼀般可以⽤来缩点，即相互到达的⼀堆点可以将他们有⽤的信息统⼀到⼀个点上去。

求解强连通分量的⽅法⼀般会使⽤Tarjan算法。

⾸先我们需要学会dfs树,定义⼏种边：树边，连接dfs树中的⽗节点和⼦节点的边。

横叉边，连接dfs树中的不在⼀个⼦树中的两个节点的边。

前向边，连接dfs树中的⼀个节点连向他的⼦树中深度差⼤于等于2，也就是不直接相连的两点的边。

后向边，连接dfs树中的⼀个节点连向他的祖先的边，⼜叫返祖边。

求解：dfn[i]表⽰i节点的时间戳，low[i]表⽰i节点的所属的强连通分量i的时间戳的最⼩值，也可以说是i或i的⼦树能够追溯到的最早的栈中节点的时间戳。

发现如果在dfs树中出现了后向边说明后向边连接的两点之间的环⼀定是强连通的，但不⼀定是最⼤⼦集。

我们有个性质：如果low[i]⽐dfn[i]⼩，说明他有⼀条连向祖宗的后向边，所以要保留在栈中。

如果当前low[i]等于dfn[i]说明他搜索的栈中没有可以连向他祖宗的边，当前栈中的点⼀定就是low[栈中的点]等于dfn[i]的点，也可以有能连向i的反向边。

有如果树边没有被找到过，则有low[u]=min(low[u],low[v]);也就是⽤v的所能连向的点的最⼩时间戳来更新u。

如果此点已经⼊栈，说明此时这是⼀条回边，因此不能⽤low[v]更新，⽽应该：low[u]=min(low[u],dfn[v]);因为，low[v]可能属于另⼀个编号更⼩的强连通分量⾥，⽽u可以连接到v但v不⼀定与u相连，所以可能u、v并不属于同⼀个强连通分量。

但是第⼀种情况如果low[v]⽐low[u]⼩的话，v⼀定有包括u的强连通分量，Tarjan求割点和桥概念：在⽆向连通图中，双连通分量分为点双和边双，点双为⼀个连通分量删去任意⼀个点都保持连通，边双为删去任意⼀条边都保持连通。

强连通算法--Tarjan个⼈理解+详解⾸先我们引⼊定义：1、有向图G中，以顶点v为起点的弧的数⽬称为v的出度，记做deg+（v）；以顶点v为终点的弧的数⽬称为v的⼊度，记做deg-（v）。

2、如果在有向图G中，有⼀条<u，v>有向道路，则v称为u可达的，或者说，从u可达v。

3、如果有向图G的任意两个顶点都互相可达，则称图 G是强连通图，如果有向图G存在两顶点u和v使得u不能到v，或者v不能到u，则称图G 是强⾮连通图。

4、如果有向图G不是强连通图，他的⼦图G2是强连通图，点v属于G2，任意包含v的强连通⼦图也是G2的⼦图，则乘G2是有向图G的极⼤强连通⼦图，也称强连通分量。

5、什么是强连通？强连通其实就是指图中有两点u，v。

使得能够找到有向路径从u到v并且也能够找到有向路径从v到u，则称u，v是强连通的。

然后我们理解定义：既然我们现在已经了解了什么是强连通，和什么是强连通分量，可能⼤家对于定义还是理解的不透彻，我们不妨引⼊⼀个图加强⼤家对强连通分量和强连通的理解：标注棕⾊线条框框的三个部分就分别是⼀个强连通分量，也就是说，这个图中的强连通分量有3个。

其中我们分析最左边三个点的这部分：其中1能够到达0,0也能够通过经过2的路径到达1.1和0就是强连通的。

其中1能够通过0到达2,2也能够到达1，那么1和2就是强连通的。

.........同理，我们能够看得出来这⼀部分确实是强连通分量，也就是说，强连通分量⾥边的任意两个点，都是互相可达的。

那么如何求强连通分量的个数呢？另外强连通算法能够实现什么⼀些基本操作呢？我们继续详解、接着我们开始接触算法，讨论如何⽤Tarjan算法求强连通分量个数：Tarjan算法，是⼀个基于Dfs的算法（如果⼤家还不知道什么是Dfs，⾃⾏百度学习），假设我们要先从0号节点开始Dfs，我们发现⼀次Dfs 我萌就能遍历整个图（树），⽽且我们发现，在Dfs的过程中，我们深搜到了其他强连通分量中，那么俺们Dfs之后如何判断他喵的哪个和那些节点属于⼀个强连通分量呢？我们⾸先引⼊两个数组：①dfn【】②low【】第⼀个数组dfn我们⽤来标记当前节点在深搜过程中是第⼏个遍历到的点。

求强连通分量的Kosaraju算法和Tarjan算法的比较一、定义在有向图中，如果两个顶点vi,vj间有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。

如果有向图的每两个顶点都强连通，则称该有向图是一个强连通图。

非强连通的有向图的极大强连通子图，称为强连通分量(strongly connected components)。

而对于一个无向图，讨论强连通没有意义，因为在无向图中连通就相当于强连通。

由一个强连通分量内的所有点所组成的集合称为缩点。

在有向图中的所有缩点和所有缩点之间的边所组成的集合称为该有向图的缩图。

例子：原图：缩图：上面的缩图中的缩点1包含：1、2,；缩点2包含：3；缩点3包含：4；缩点4包含：5、6、7。

二、求强连通分量的作用把有向图中具有相同性质的点找出来，形成一个集合（缩点），建立缩图，能够方便地进行其它操作，而且时间效率会大大地提高，原先对多个点的操作可以简化为对它们所属的缩点的操作。

求强连通分量常常用于求拓扑排序之前，因为原图往往有环，无法进行拓扑排序，而求强连通分量后所建立的缩图则是有向无环图，方便进行拓扑排序。

三、Kosaraju算法时间复杂度：O（M+N）注：M代表边数，N代表顶点数。

所需的数据结构：原图、反向图（若在原图中存在vi到vj的有向边，在反向图中就变成为vj到vi的有向边）、标记数组（标记是否遍历过）、一个栈（或记录顶点离开时间的数组）。

算法描叙：步骤1：对原图进行深度优先遍历，记录每个顶点的离开时间。

步骤2：选择具有最晚离开时间的顶点，对反向图进行深度优先遍历，并标记能够遍历到的顶点，这些顶点构成一个强连通分量。

步骤3：如果还有顶点没有遍历过，则继续进行步骤2，否则算法结束。

hdu1269（Kosaraju算法）代码：#include<cstdio>#include<cstdlib>const int M=10005;struct node{int vex;node *next;};node *edge1[M],*edge2[M];bool mark1[M],mark2[M];int T[M],Tcnt,Bcnt;void DFS1(int x)mark1[x]=true;node *i;for(i=edge1[x];i!=NULL;i=i->next) {if(!mark1[i->vex]){DFS1(i->vex);}}T[Tcnt]=x;Tcnt++;}void DFS2(int x){mark2[x]=true;node *i;for(i=edge2[x];i!=NULL;i=i->next) {if(!mark2[i->vex]){DFS2(i->vex);}}}int main(){int n,m;while(scanf("%d%d",&n,&m)){if(n==0&&m==0){break;}int i,a,b;for(i=1;i<=n;i++){mark1[i]=mark2[i]=false;edge1[i]=NULL;edge2[i]=NULL;}node *t;while(m--){scanf("%d%d",&a,&b);t=(node *)malloc(sizeof(node));t->vex=b;t->next=edge1[a];edge1[a]=t;t=(node *)malloc(sizeof(node));t->vex=a;t->next=edge2[b];edge2[b]=t;}Tcnt=0;for(i=1;i<=n;i++){if(!mark1[i]){DFS1(i);}}Bcnt=0;//Bcnt用于记录强连通分量的个数for(i=Tcnt-1;i>=0;i--){if(!mark2[T[i]]){DFS2(T[i]);Bcnt++;}}if(Bcnt==1)//如果强连通分量的个数为1则说明该图是强连通图{printf("Yes\n");}else{printf("No\n");}}return 0;}四、Tarjan算法时间复杂度：O（M+N）注：M代表边数，N代表顶点数。

图论之 Tarjan及其应用一、Tarjan应用1.求强连通分量2.求lca3.无向图中，求割点和桥二、图的遍历算法（一）、宽度优先遍历(BFS)1、给定图G和一个源点s, 宽度优先遍历按照从近到远的顺序考虑各条边. 算法求出从s到各点的距离。

宽度优先的过程对结点着色.白色: 没有考虑过的点（还没有入队的点）黑色: 已经完全考虑过的点（已经出队的点）灰色: 发现过, 但没有处理过, 是遍历边界（队列中的点）依次处理每个灰色结点u, 对于邻接边(u, v), 把v着成灰色并加入树中, 在树中u是v的父亲(parent)或称前驱(predecessor). 距离d[v] = d[u] + 1整棵树的根为s（二）、深度优先遍历(DFS)1、初始化: time为0, 所有点为白色, dfs森林为空对每个白色点u执行一次DFS-VISIT(u)时间复杂度为O(n+m)2、伪代码三、DFS树的性质1、括号结构性质对于任意结点对(u, v), 考虑区间[d[u], f[u]]和[d[v], f[v]], 以下三个性质恰有一个成立: 完全分离u的区间完全包含在v的区间内, 则在dfs树上u是v的后代v的区间完全包含在u的区间内, 则在dfs树上v是u的后代2、定理(嵌套区间定理):在DFS森林中v是u的后代当且仅当d[u]<d[v]<f[v]<f[u], 即区间包含关系. 由区间性质立即得到。

四、边的分类1、一条边(u, v)可以按如下规则分类树边(Tree Edges, T): v通过边(u, v)发现后向边(Back Edges, B): u是v的后代前向边(Forward Edges, F): v是u的后代交叉边(Cross Edges, C): 其他边，可以连接同一个DFS树中没有后代关系的两个结点, 也可以连接不同DFS树中的结点。

判断后代关系可以借助定理12、算法当(u, v)第一次被遍历, 考虑v的颜色白色, (u,v)为T边灰色, (u,v)为B边(只有它的祖先是灰色)黑色: (u,v)为F边或C边. 此时需要进一步判断d[u]<d[v]: F边(v是u的后代, 因此为F边)d[u]>d[v]: C边(v早就被发现了, 为另一DFS树中)时间复杂度: O(n+m)定理: 无向图只有T边和B边(易证)3、实现细节if (d[v] == -1) dfs(v); //树边, 递归遍历else if (f[v] == -1) show(“B”); //后向边else if (d[v] > d[u]) show(“F”); // 前向边else show(“C”); // 交叉边注：d(入栈时间戳）和f 数组（出栈时间戳）的初值均为-1, 方便了判断四、强连通图1、在有向图G 中，如果两点互相可达，则称这两个点强连通，如果G 中任意两点互相可达，则称G 是强连通图。

Tarjan算法Taijan算法是求有向图强连通分量的算法。

Tarjan 算法主要是在 DFS 的过程中维护了⼀些信息：dfn、low 和⼀个栈。

1. 栈⾥存放当前已经访问过但是没有被归类到任⼀强连通分量的结点。

2. dfn[u] 表⽰ DFS 第⼀次搜索到 u 的次序。

3. Low(u) 记录该点所在的强连通⼦图所在⼦树的根节点的 Dfn 值。

基本思路： 在深度搜索中会搜索到已访问的节点，产⽣环，即连通分量的⼀部分，环与环的并集仍是连通分量。

由于深度搜索总是会回溯，所以将强连通图中最早搜索到的节点认为是根节点，它的dfn 和 low都是最⼩的。

之后会深度搜索⼦树的所有节点，确定所有与回边相关的环，在出现环时，环上的节点的值就会统⼀为环上最⼩的值。

直到回溯到根节点 dfn = low 的标志，输出连通分量，其他节点low相同，但dfn要⽐根节点⼤。

⾄于（ u， v ）访问到新的节点，在初始化下 v 的 low 值是递增的，但是 v 在进⼊深度搜索后，它返回的值会变化。

当 v 出现在环中被处理了， v 的 low 值会变⼩。

此时 u 也⼀定在环中， v 的low 值变⼩，是由于有⼀条回边连接到的 u 的⽗辈的节点，⽗辈的节点 - 顶点 - u - v - ⽗辈的节点构成了⼀个环。

伪码解析：Tarjan(u){DFN[u]=Low[u]=++Index // 为节点u递增地设定次序编号和Low初值Stack.push(u) // 存放已经访问过但没有被归类到任⼀强连通分量的结点for each (u, v) in E //深度搜索if ( v is not visted ) { Tarjan( v )　Low [ u ] = min( Low[ u ] , Low[ v ] ); // 初始化下 low[ v ] ⽐较⼤，若 low [ v ]变⼩， v 在环中，u 也在环中，且两个环相连通。

}else if (v in S) // 如果节点v还在栈内，出现回边，出现环Low [ u ] = min( Low[ u ], DFN[ v ] )if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根v = S.pop // 将v退栈，print vuntil (u== v)}。

Tarjan算法详解刚学的⼀个新算法，终于有时间来整理⼀下了。

想必都对著名的 ‘太监’ 算法早有⽿闻了吧。

Tarjan Tarjan 算法是⼀种求解有向图强连通分量的算法，它能做到线性时间的复杂度。

实现是基于DFS爆搜，深度优先搜索⼀张有向图。

！注意！是有向图。

然后根据树，堆栈，打标记等种种神奇扯淡⽅法来完成拆解⼀个图的⼯作。

如果要理解Tarjan，我们⾸先要了解⼀下，什么叫做强连通。

强连通 ⾸先，我们将可以相互通达的两个点，称这两个点是强连通的。

⾃然，对于⼀张图，它的每两个点都强连通，那么这张图就是⼀张强连通图。

⽽⼀张有向图中的极⼤强连通⼦图就被命名为强连通分量。

那么，举个栗⼦吃吧。

（盗图⼩丸⼦光荣上线，come from 百度） 对于上⾯的那张有向图来说，{1,2,3,4}，{5}，{6}分别相互连通，是这张图的三个强连通分量。

算法思想简解 Tarjan是在dfs的基础上将每⼀个强连通分量当做搜索树种的⼀个⼦树的遍历⽅法。

那么我们就可以在搜索的时候，将当前的树中没有访问过的节点加⼊堆栈，然后在回溯的时候判断栈顶到其中的节点是否是⼀个强连通分量。

故⽽我们在遍历的时候，定义如下变量来记录我们的遍历过程。

1.dfn[i]=时间戳（节点i被搜索的次序） 2.low[i]=i或i的⼦树所能寻找到的栈中的节点序号。

所以，当dfn[i]==low[i]时，i或i的⼦树可以构成⼀个强连通分量。

算法图解（盗图愉悦） 在这张图中我们从节点1开始遍历，依次将1， 3，5加⼊堆栈。

当搜索到节点6时，发现没有可以向前⾛的路，开始回溯。

回溯的时候会发现low[5]=dfn[5],low[6]=dfn[6]，那么{5}，{6}分别是两个强连通分量。

直到回溯⾄节点3，拓展出节点4. 结果⾃然就是拓展到了节点1，发现1在栈中，于是就⽤1来更新low[4]=low[3]=1; 然后回溯节点1，将点2加⼊堆栈中。

数据结构课设有向图强连通分量求解数据结构课设：有向图强连通分量求解一、引言有向图是图论中的一种重要概念，强连通分量是有向图中的一个子图，其中任意两个顶点之间都存在一条有向路径。

在数据结构课设中，我们需要实现一个算法，能够求解给定有向图的强连通分量。

二、问题描述给定一个有向图G=(V,E)，其中V表示顶点的集合，E表示边的集合。

我们需要设计一个算法，能够找出图G中的所有强连通分量，并将其输出。

三、算法设计为了解决这个问题，我们可以使用Tarjan算法，该算法是一种经典的强连通分量求解算法。

下面是Tarjan算法的详细步骤：1. 初始化步骤：- 创建一个空栈S，用于存储访问过的顶点。

- 创建一个整数数组dfn和low，用于记录每个顶点的访问次序和最早访问到的祖先顶点的次序。

- 创建一个布尔数组inStack，用于标记顶点是否在栈中。

- 创建一个整数变量index，用于记录当前访问的次序。

2. 递归搜索步骤：- 遍历图中的每个顶点v，若v未被访问，则执行递归搜索函数Tarjan(v)。

- 在Tarjan(v)函数中，首先将v入栈，并标记v在栈中。

- 然后将dfn[v]和low[v]均设为index的值，并将index加1。

- 对于v的每个邻接顶点u，若u未被访问，则执行递归搜索函数Tarjan(u)。

- 在递归返回后，更新low[v]的值为v的所有邻接顶点u的low值的最小值。

- 若dfn[v]等于low[v]，则说明v是一个强连通分量的根节点，将栈中的顶点依次出栈，直到v为止，并将这些顶点构成一个强连通分量。

3. 输出结果：- 将找到的所有强连通分量输出。

四、算法分析Tarjan算法的时间复杂度为O(V+E)，其中V为顶点的数量，E为边的数量。

该算法通过深度优先搜索的方式遍历图中的每个顶点，同时使用dfn和low数组记录顶点的访问次序和最早访问到的祖先顶点的次序。

通过比较dfn和low数组的值，可以确定强连通分量的根节点，并将其输出。