Tarjan

谈谈Tarjan的算法

区分一下白点,灰点,黑点。

白点:未访问过的点。

灰点:正在访问的点。

黑点:已经访问的点。

NO.1.有向图的强联通分量

    何为强联通,就是在有向图中,任意两个点之间能相互到达,则称两个顶点强联通。

    经过分析,其实也是比较简单的,就是一次dfs的遍历,进入一个顶点后,记录当前节点以及它的父亲,因为是强联通分量,父亲记不记也没玩什么关系,主要是看你要不要记录这条路。

    然后就搜索有它的儿子节点,先判断它是否已经到过,即是否为白点,如果是的话,就dfs这个点,然后low[u]=min(low[u],low[v]);如果不是的话,就判断是否在栈中,即是否为灰点,如果

    不是灰点的话,就表示是黑点了,那么就不用去管了,因为,黑点是灰点时无法到达当前这个强联通,所以,这一定是不同的两个强联通,如果是灰点的话low[u]=min(low[u],dfn[v]).然后

    要缩点的话就是,将dfs[x]==low[x]的时候就是直接进行出栈操作就可以了。

NO.2 割点,这概念是在无向图中的,没有讲无向图的双联通分量直接上割点,割边不太好。

    割点的判断有几个条件

    (1)如果是根节点,则判断是否有多棵子树,如果>=2 则为割点。

    (2)如果为其余的节点,则判断,该点及其子孙节点能否到达该点的祖先,如果不行,则该点为割点。

NO.3 桥,这个就更加简单了,这个的话就是判断该边能否到达其上一个点,如果不能,则为割边。

原文地址:https://www.cnblogs.com/fengzhiyuan/p/7123374.html