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

-_-#上面的ccs应该是scc,名字叫错了跪。。。

关于Tarjan,https://www.byvoid.com/blog/scc-tarjan这个讲的挺好,一定要看看。然后我说下我自己咋想的。

首先初始化,对于每个节点都要分配一个dfn值和low值,开一个tim当作计时器,然后基本的流程就是:

~进入当前节点
~tim++
~当前节点dfn=low=tim
~标记当前结点已经走过(注意图的遍历中节点只会走一次,也就是说标记不用撤销)
~把当前节点压入栈中(这个stack预先开好了)
~开始扫当前节点的分支,如果这个分支走过了,判断一下是不是这个分支是不是在栈里,如果在栈里的话就看看分支的dfn是不是比当前节点的low还小,小的话就把当前的low值调成那个dfn值;如果分支没走过,直接递归进到那个分支里去,等到递归出来之后,如果分支的low值比当前low值小,就令当前low值为分支low值(这步比较难懂)
~等到所有分支扫完,检查一下当前的dfn是不是等于low,如果不相等直接退出当前递归就好;相等的话,说明节点是scc的根,这个时候不断弹出栈,直到当前节点也被弹出,弹出的这些节点放在一起就是一组scc。

其实这个Tarjan的原理就是利用时间标记,进入栈的节点都是预定互相连通的,dfu值的意思就是当遍历到这个节点,是第几步(我把tim当作步来看),low的意思就是从当前节点可以走到的尽量在时间上先走到的栈内节点对应的dfu,就是最优解的对应标号,这个low肯定是越小越好,因为low越小我们的连通回路就越大。如果low=dfu,那就是当前个点已经没有办法和栈里的既有的点连通了,所以当尝试了全部的走法之后还是没有找到一个栈里的节点来和当前点连通,就说明这个连通回路闭合了,这个时候只要把整个连通回路统统从栈里弹出来,就能得到整个连通回路,也就是scc的一个。每步中接下来要走的节点有三种情况:有的节点访问过但是不在栈里,这样的点不用考虑,因为它已经被弹出了,相当于这个节点已经和我们没关系了;有的点访问过而且在栈里,这样的节点有可能就是当前连通回路的终点了,所以我们要比较一下当前low值是不是比它的dfu大,如果大的话说明这个点可以连通过去,如果小的话说明我们已经有一种连通方式可以包括和它连通了,这个不是最优解,我们就忽略好了;有的节点没访问过,这样的点我们要递归进去处理一下,递归完之后这个节点就有了它在当前情形下该有的dfu和low了,因为这个点和当前点连通,所以这个点要是有一个比当前更好的连通方案,我们用它的就好。

基本就是这么搞,这种时间流逝标记的方法很重要(虽然我还不知道到底有多重要。。。)。

 

Leave a Reply

Scroll to top