草庐IT

tarjans-algorithm

全部标签

Tarjan算法求割点

定义如果在一个图中,删除某个节点连同与之关联的边,会导致整个图的连通分支数增加,那么这个节点叫做割点(ArticulationPoint,CutVertex)如下图:整个图的连通分支数为1,但是删除节点3后,整个图就“分裂”成了2个连通分支:因此,节点3是整个图的割点。方法一个很容易想到的方法是,依次删除图中的每一个节点,看剩下部分的连通分支数增没增加。但是那样显然太浪费时间了!有没有一种办法,能够快速的找出整个图的割点呢?Tarjan算法的核心思想:深度优先遍历(DFS)这张图,得到的DFS树(由遍历路径和节点构成的树)中,当某个节点u满足以下条件之一时,它就是割点:u为DFS树的树根,且u

Tarjan算法求割点

定义如果在一个图中,删除某个节点连同与之关联的边,会导致整个图的连通分支数增加,那么这个节点叫做割点(ArticulationPoint,CutVertex)如下图:整个图的连通分支数为1,但是删除节点3后,整个图就“分裂”成了2个连通分支:因此,节点3是整个图的割点。方法一个很容易想到的方法是,依次删除图中的每一个节点,看剩下部分的连通分支数增没增加。但是那样显然太浪费时间了!有没有一种办法,能够快速的找出整个图的割点呢?Tarjan算法的核心思想:深度优先遍历(DFS)这张图,得到的DFS树(由遍历路径和节点构成的树)中,当某个节点u满足以下条件之一时,它就是割点:u为DFS树的树根,且u