Tarjan算法初探 (1):Tarjan如何求有向图的强连通分量

在此大概讲一下初学tarjan算法的领悟( qwq)

 

tarjan算法 是图论的非常经典的算法 可以用来寻找有向图中的强连通分量 与此同时也可以通过寻找图中的强连通分量来进行缩点

首先给出强连通分量的定义：

若在有向图g中 存在u到v的路径的同时也存在v到u的路径 则称u与v是强连通的 若g中所有点之间两两之间是强连通的则称g为一个强连通图 一个有向非强连通图的极大强连通子图称为强连通分量

极大强连通子图:g是一个极大强连通子图 当且仅当g是一个强连通图 同时不存在另一个强连通图g'使g是它的真子集

下面 的2 3 4 三个点构成一个强连通分量 同时1也是一个强连通分量

 

 

通过观察强连通分量的定义我们可以发现 如果通过dfs遍历含有强连通分量的图 一个点可能与它的子节点在同一个强连通分量中 或者与父节点在同一个强连通分量 若点v延伸出的dfs搜索树中有节点跟v有连边就意味着这个节点回溯回来的路径上的所有点与v强连通 同时点v延伸的搜索树中不一定只有一个节点满足这样的条件 而当把这样的节点找全以后 就求出了以v节点为根节点的搜索树中所有与v强连通的点

但是这样操作并没有考虑v的父节点或祖父节点即此时求得的并不一定是一个强连通分量只能说明这些点强连通 但最终一定能求出包含dfs起点的强连通分量（以dfs起点为根节点的搜索树中必定包含所有与起点强连通的点）

但若要求求出所有强连通分量 则不管算法的时间复杂度 求出整张图的强连通分量需要暴力枚举每一个点才能得到所有强连通分量 而这样时间复杂度会达到n² 级别

看起来不错但操作过于暴力所以让我们想一想有没有更好的做法？在遍历v的搜索树时 它的子节点不仅可能有边连接v 还可能连接到v的父节点或祖先节点或其他与v强连通的点 有没有什么方法能够利用这一点来简化算法？或者怎样唯一确定v是一个强连通分量的根节点？（确定一个点v 而所有与v强连通的点在以v为节点的搜索树中）

 

若以1点为dfs起点可以求出包含1的强连通分量 但不能在搜索完以2点为根节点的搜索树时判断2是否是一个强连通分量的根节点

接下来正式开始介绍tarjan算法：

tarjan算法基于dfs

强连通分量在dfs中的根节点延伸的搜索树中包含所有与根节点强连通的点（废话）

强连通分量是由环构成（废话*2）

那么一个点v是一个强连通分量的根节点的条件是在它的搜索树中没有节点能访问到它的父节点或祖先 否则v可与它的父亲或祖先节点构成一个环故与v强连通的点的集合属于与v的父亲或祖父节点强连通的点的集合 同时点v若与它的祖父节点或父节点相连 那么它的祖父或父亲节点所在强连通分量的根节点显然与点v所在的强连通分量的根节点相同

再然后在dfs搜索的过程中搜索与回溯的过程相当于一个栈而子节点在栈中永远在父节点的上方 那么一个强连通分量的根节点在栈中时也必然在与它所有强连通的点的下方 而平时回溯时会直接退栈而我们在回溯时判断此时的节点是不是强连通分量的根节点 是 将当前点和在当前点之上的所有点取出 这些点共同构成一个强连通分量 不是 则保留栈中节点

因为一个节点若不是强连通分量的根节点 那由它搜索下去必定与栈中的某个节点v'之间所有的节点构成一个环而环上所有点之间强连通 又因为强连通分量的根节点在栈中必然在与它所有强连通的点下方故v'便是此时这个节点所在强连通分量的根节点 而且由以上操作可知留在栈中的点属于某个以栈中某个点为根节点的强连通分量 同时由dfs特性知回溯到某个强连通分量的根节点时栈中在它之上的点不可能属于此根节点之下的强连通分量否则说明该节点不是根节点因为它的子节点可以与父节点或祖先节点相连 

具体代码实现时可以维护一个low[v]  low[v]记录的是v所属于的强连通分量的根节点的dfs序  由dfs序可知强连通分量的根节点的dfs序是整个强连通分量中最小的 那么搜索完后只需要判断low[v]是否等于v的dfs序即可知v是否为强连通分量的根节点 而显然low[v]=min(low[to],low[v]),to∈v的子节点 而当v连接的是已经在栈中的点v'时则low[v]=min(low[v],v'的dfs序) 

 

算法时间复杂度：

显然tarjan算法中每一点都只会进栈一次出栈一次 而每一个节点都会遍历它的所有边 故tarjan算法求有限图中的强连通分量的时间复杂度为t(n+m)

代码以后补齐：