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算法内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复