计算图的关节点

图的关节点:

  如果删去某个节点及依附在该节点上的边后,该图被分割为两个或两个以上的连通图,则该节点为关节点。

计算关节点的关键思路:

  在该图的深度优先生成树上,如果某个节点的孩子节点(不一定是二叉树,孩子节点可能大于2)的子树中,所有孩子节点的子树中都有回边能回到该节点的祖先上,则该节点不是关键节点,因为即使删除了该节点,该节点的祖先或它的孩子都能通过回边将彼此连结起来。与之对应,如果该节点的孩子节点中,但凡有一个孩子节点的子树中没有回边,则该节点一定为关键节点,因为即使其他的孩子节点都有回边,但删除该节点后,这个没有回边的孩子节点还是与被删节点的祖先间分割开了。

一点不是问题的问题:

  对于当前节点v,在不考虑v是整个树的根节点的情况下,v只有在它的某一个子树w中,w及w的子节点里不存在到v的父母或祖先节点的回边的情况下,v才是关键节点(只有在v的所有的孩子节点的子树上都有回边才不算关键点,P177中,G5的B只有在C上才有回边,因此B仍然为关键节点)。

  现在对low(v):

Low(v)在visited[v],low[w],visited[k]中找最小值,w为v的孩子节点,k为与v有回边的父母或祖先节点。

首先看vistited[v],对visited[v]来说,它是v的被访问顺序,由于访问时使用的前序遍历,因此越靠近叶子节点的节点visited值越大。

再看low[w],low[w]是用于统计v的孩子节点的回边的情况的,现在加入v没有回边回到它的祖先的回边,但如果它的子节点w有或w的子节点里有,则等价于v也有了这个回边,因为v可以通过w来访问到v的祖先。

  对于visited[k],这个用于统计v到祖先的回边。

Low(v)的过程,实际上就是比较visited[v],low[w],visited[k]的大小,如果low[w]最小,说明v的子节点w的子树中有回边到v的祖先,如果visited[k]最小,说明v有到v的祖先的回边。

计算得到的low(v),是用于判断v的父亲节点是否为关键节点的,因为low(v)是v所能到达的最浅的节点,它要么是它被访问的顺序(visited[v]),要么是通过子树回边到达的最浅节点(low(w)),要么是通过自己的回边到达的最浅节点(visited[k])。

对一个节点,当它的孩子节点的最浅节点小于它的被访问顺序,也就是low[w]<visited[v]时,说明v的孩子节点中有回边绕过了v到达了v的祖先。如果v的所有孩子节点都有这样的回边,则删除v后祖先节点一样能通过回边访问到v的孩子,而不影响连通性。

而如果只要有一个孩子节点使low[w]>=visited[v],也就是代表该孩子节点无法绕过v,则v就是关键节点,因为祖先节点无法绕过v访问这个孩子。

原文地址:https://www.cnblogs.com/lxy-xf/p/11283811.html