我是靠谱客的博主 大胆口红,这篇文章主要介绍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没有被更新),那么就从栈里面弹出值,直到弹到他自己这就是一个强连通分支了。

最后

以上就是大胆口红最近收集整理的关于tarjian算法 最大强连通分支的全部内容,更多相关tarjian算法内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(40)

评论列表共有 0 条评论

立即
投稿
返回
顶部