浅谈Tarjan
干啥的
Tarjan是用来求强连通分量的算法
有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量。
是不是看不懂?举个栗子
这个图中的强连通分量有${0,1,2},{4},{3}$。
tarjan算法的过程大概就是DFS,上代码!
|
|
有啥用
1.缩点
有时候在一张图上出现了环,于是很多事情变得不太方便会卡死,这时候缩点就很有必要了,你可以把一个有环的图变成有向无环图。
用上面的图举个例子吧
缩点前
缩点后
这个点6就包括了点1,2,3。
2.割点
在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。 如果某个割点集合只含有一个顶点X(也即{X}是一个割点集合),那么X称为一个割点。
就是说这个点删除后强连通块增加了,那么这个点就是割点,如图,点1即为割点
怎么求割点呢?
其实和之前强连通分量中的tarjan差不多了,如果这个点的dfn比low要小,说明他的子树中没有能够到达他祖先的点,他是这个双连通分量的一个割点,但要加一个特判,根节点如果有两个及以上的儿子,那么他也是割点。