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

知识点:
(1)有向图:由有向边构成的图(这是Tarjan算法的前提和条件)
(2)强连通:如果两个顶点可以互相通达,则称两个顶点强连通。如果有向图G的每两个顶点都强连通,则称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量

Tarjan算法:
Tarjan算法是用来求强连通分量的,它是一种基于DFS的算法,每个强连通分量为搜索树中的一棵子树。并且运用了数据结构栈。

引入两个非常重要的数组:

(1)dfn[]:时间戳(被搜到的次数),一旦某个点被DFS后,这个时间戳就不再改变(且每个点只有唯一的时间戳)。所以经常根据dfn的值来判断是否需要进行进一步的深搜。

(2)low[]:该子树中,且仍在栈中的最小时间戳,像是确立了一个关系,low[]相等的点在同一强连通分量中。

注意初始化:dfn[] = low[] = ++cnt;

思路:

首先这个图不一定是个连通图所以跑Tarjan的时候要枚举每一个点,若dfn[]==0,进行深搜。

然后对于搜到的点寻找与其有边相连的点,判断这些点是否已经被搜索过,若没有,则进行搜索。若该点已经入栈,说明形成了环,则更新low.

在不断深搜的过程中如果没有路可以走了(出边遍历完了),那么就进行回溯,回溯时不断比较low[],取最小的low值。如果dfn[x]==low[x],则x可以看作某一连通分量子树的根,也说明了找到了一个强连通分量,然后对栈进行弹出操作,直到x被弹出。

图片说明

手动模拟:
从1开始:dfn[1] = low[1] = ++cnt = 1 , 1入栈 ,栈:1
1到2 :dfn[2] = low[2] = ++cnt = 2 , 2入栈 ,栈:1,2
2到4 :dfn[4] = low[4] = ++cnt = 3 , 4入栈 ,栈:1,2,4
4到6 :dfn[6] = low[6] = ++cnt = 4 , 6入栈 ,栈:1,2,4,6
6无出度,之后判断dfn[6] == low[6],说明6是一个强连通分量的根节点:6及6以后的点出栈并输出(6无出度,说明可以进行回溯,回溯的时候不断进行low的比较,取最小的low,如果low[]==dfn[],说明找到了根)

回溯到4,发现4找到了一个已经在栈中的点1,,更新low[4] = min(low[4] , dfn[1]) ,于是low[4] = 1.

从4回溯到2,low[2] = min(low[4],dfn[1]),于是low[2]=1.

由2回溯到1,low[1] = min(low[1],low[2]) = 1.

然后更新3,更新3的过程忽略,更新完之后,1的所有出边就跑完了
于是判断:low[1] == dfn[1]说明以1为根节点的强连通分量已经找完了。将栈中1以及1之后进栈的所有点,都出栈并输出。