tarjan求图的联通性问题是一种高效的模板化方法。其依赖于dfndfnlowlow求解,十分巧妙。
kosaraju依赖更加巧妙的性质,证明略为复杂。

本文递交已结束。

tarjan求解

对于一棵树树,其各节点时间戳如下图:

研究树的联通性问题是没有意义的,除了时间戳(dfndfn)外,另外引入一个追溯值(lowlow)记录对于一个节点uu其本身及其深度优先搜索子树所有点可以回到的最小的时间戳,对于一个普通的有向图其深度优先搜索时间戳[]及追溯值() 为:

割点判定法则:在无向图中,当某一点uu,其任意一个出边所连的点vv 当且仅当满足dfn[u]<=low[v]dfn[u]<=low[v](该点有一个子树中所有的点都没有办法追溯回uu 的祖先,则当将uu 删除时该子树会断开)时uu 为该图的割点,特别的若uu 为根节点,只要有超过两个子节点即为割点。

割边判定法则:在无向图中,与求解割点类似的在深度优先搜索生成树中某一条边(u,v)(u,v),当且仅当dfn[u]<low[v]dfn[u]<low[v]时,该边为割边。

强连通分量的求解方法:在有向图的深度优先搜索生成树中若存在某一点uu当满足dfn[u]=low[u]dfn[u]=low[u]时,uu 与其子树中所有的点都在同一个强连通分量中。利用栈记录下搜索顺序,当找到一个节点uu 时从栈顶到栈中的uu之间的所有元素即为其子树,它们在同一个强连通分量中。

Kosaraju求强连通分量

谭老师在课堂上详细地证明了Kosaraju的正确性,证明思路较为复杂。Kosaraju与Tarjan思路相类似,首先在图中任选一个节点的作为起点开始dfs,按照退出的顺序给节点编号就是搜索森林的后序序列。再每次选择未访问的标号最大的点进行搜索,其搜索树的节点都在同一个强连通分量中。

证明是比较复杂的。首先对于第一次搜索,编号小的到编号大的一定存在一条直接路径,除非它们不在同一棵树中。将图求逆后,编号小的一定不能再通过原来的路径到达编号大的,那么从编号大的节点开始dfs一遍,能够到达的节点在原图一定至少存在两条路径是让它们互相相连的。

评论