tarjian算法最大强连通分支

60 阅读 0 评论 40 点赞

我是靠谱客的博主大胆口红，这篇文章主要介绍tarjian算法最大强连通分支，现在分享给大家，希望可以做个参考。

tarjian算法是利用DFS寻找最大连通分支的算法，算法只需要对图进行一次DFS，无论时间复杂度还是代码复杂度都不是太高。

思路就是先利用DFS构造一棵树，那么分成四种边——树边、前向边、后向边、交叉边。前向边在环中等价于树边（请画图验证），因此直接忽略，交叉边在树中不构成环（依然画个图...），只有后向边构成环（还是画个图），因此，重点就是利用后向边，找到此点的成环的祖先，再找到同祖先且成环的点，这个环就构造成了。

关键是怎么寻找这个祖先呢？

巧妙的是tarjian大人使用了一个low（祖先）和一个栈（被遍历过但未处理的点）来记录信息。

首先是栈，如果DFS到一个点u，先把此点的LOW[u]=DFN[u]=index ( 解释一下，index是这个点被遍历的顺序，也就是时间戳 ) 就把这个点压到栈中，然后继续进行DFS，

如果一个点u有边指向栈中的点V，也就是有后向边了，这时候使得LOW[u]=DFN[v]，继续进行DFS，当对其子节点的DFS结束的时候，要判断一下，是其子节点的LOW小还是自己的LOW小（因为其子节点可能因为后向边而使得LOW被更新为其祖先的LOW），如果小的话，就把自己的LOW更新为子节点的LOW。然后直到某点的DFS结束，若这个点的DFN=LOW，那么这个点就是一个祖先节点（他没有后向边，他的子节点也没有指向比他更祖先的后向边，因此他的LOW没有被更新），那么就从栈里面弹出值，直到弹到他自己这就是一个强连通分支了。