我理解的Tarjan算法

Tarjan算法是线性时间求解有向图强连通分量(SCC)的算法,它曾一度把我搞到头皮发麻。如今国内的教程基本来自于byvoid大神的博客,包括我高中时期的OI老师的课件和代码也是从此处来的。这么多年来,虽然能用这个算法解决一些算法题,但是有几个点还是不甚理解。直到我在YouTube上看到了“Tarjans Strongly Connected Components algorithm | Graph Theory – WilliamFiset”这个视频,之前的一些疑问得以解开,因此记录下这篇博文。

一些概念

强连通分量

有向图的强连通分量(SCC)是指它的极大强连通子图,这里强调“极大”和“强连通”。强连通是指在这个子图里面的点两两可达。极大与数学中的极大的定义是类似的,如果当前子图与原来的有向图相等,并且满足强连通,那么它一定是SCC,如果当前子图与原来的图不等(真子图),那么这个子图再加上原图中其他的任意一点则不构成强连通分量。这里可以参考:Strongly connected component – wikipedia

DFS时间戳

即用深度优先搜索遍历这张图时按照时间顺序给每个节点进行编号。以下图为例,如果从左上角的点开始做DFS,每个点的时间戳如图所示。


Low函数(Low Link Value)

BYVoid大神将Low(u)解释为u或u的子树能够追溯到的最早的栈中节点的次序号(上文:Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。)。现在我是理解这句话的含义的,但是第一次看到这句话的时候我很懵圈。

要想搞清楚这句话的含义,我们先看一下原图中有哪些强连通分量。



如图所示,我将同一个强连通分量中的点用同样的颜色表示。每个点上的数字就是上面我们讲到的DFS时间戳。我们先忘记BYVoid大神对Low函数的定义,现在我告诉你每个点Low函数的值就应该等于这个点所在的强连通分量中最小的DFS时间戳。


假设每个点的ID就是这个点的DFS时间戳:在强连通分量$\{1,2,3\}$中,每个点的Low值就等于这个强连通分量中最小的DFS时间戳$1$;在强连通分量$\{4,5\}$中,每个点的Low值就等于这个强连通分量中最小的DFS时间戳$4$;在强连通分量$\{6\}$中,每个点的Low值就等于这个强连通分量中最小的DFS时间戳$6$。

也许到这里你还不能完全理解BYVoid大神的解释,请继续往下看。

关于算法

栈的“不变式”(The Stack Invariant)

你不用理解什么叫不变式,也不用为什么这里叫栈的不变式(当然理解的话更好)。

Tarjan算法是基于DFS的,为了我们从随机的任意一个点开始DFS都可以找到所有的强连通分量,Tarjan算法维护了一个集合(通常用栈来实现),这个集合很神奇,维护好这个集合就可以井然有序地更新每个点的Low值。

我们用如下的方法来维护这个集合(栈):

  • 当每个点第一次被发现时,入栈;
  • 那么按照上一点,栈中一定有连续的一段包括了一个强连通分量里的所有点。我们通过某些方法找到一个强连通分量之后,把这个强连通分量中的所有点出栈。

Low函数更新规则:

如果u和v是图中的两个点,当我们正在DFS的点为u时,我们拓展所有u的邻接节点,Low值的更新方法是:用Low(v)来更新Low(u)当且仅当从u到v是有边的,并且u试图发现v的时候v已经在栈中了。

v已经在栈中可以说明很多事情,首先是v已经被访问(DFS)过了,他已经不是第一次被发现了。我们还能知道u一定是v的后代,u到v的边是一条返祖边,并且我们可以确信u和v属于同一个强连通分量。其实这就揭示了寻找强连通分量的本质就是寻找返祖边,也可以说是寻找环。

如何判断找到一个强连通分量

按照上面的Low函数更新规则,我们可以发现DFS的过程一边拓展节点,一边更新Low值。当我们做完所有节点拓展之后,如果Low值与DFS时间戳是相等的,说明这个点的时间戳就是这个强连通分量中最小的时间戳,那么我们就找到了一个强连通分量。为什么呢?这个强连通分量在哪里呢?这个强连通分量中的所有的点都堆在栈顶的一个连续空间内。如果你不能理解的话,请继续往下看。

算法描述

  • 开始DFS,为当前DFS的点分配时间戳,让它的Low值预设为于与时间戳相等,打访问标记,把该点入栈;
  • 拓展邻接节点,如果被拓展到的节点没有被分配DFS时间戳(没有被访问过)就DFS这个点,如果已经被分配时间戳并且在栈中,把当前点的Low值更新为当前点和拓展点的Low值中较小的一个,如果已经分配但不在栈中,说明这个被拓展的点已经找到它所在的强连通分量了(已经处理完毕),所以不用管这个点;
  • 在拓展完所有的邻接节点之后,如果Low值仍然和DFS时间戳相等,说明找到了强连通分量,我们开始执行退栈操作,一直到当前这个点(Low值与DFS时间戳相等的点)退栈结束为止。
  • 这其中为了判断一个点在不在栈内,我们可以用一个数组inStack来标记,进栈就标记为1,退栈标记为0。

代码实现

模拟过程

理解算法最好的方法就是模拟。由于这篇日志写的匆忙,就不画模拟图了,想看模拟的可以去BYVoid大神的博客或者文章开头提到的Youtube频道看一看。以后如果有空的话我会把这一部分补上。

参考资料

后记

向各位前辈致敬。

如果文章中存在错误,欢迎大家在评论区留言。

转载请注明出处:ZhaoYuwei的博客

说点什么

avatar
50
  Subscribe  
提醒