无向图点连通性的求解及应用

Published on 2016 - 06 - 22

关节点的求解

求关节点的朴素方法

判断关节点的一种朴素方法是从关节点的定义出发,依次去掉每个顶点(及其所关联的边),然后用DFS去搜索整个图,可得到该图的连通分量个数,如果是大于2,则该顶点是关节点。该方法的复杂度较高,为O(n^3)。当然,具体实现时并不真正需要去掉每个顶点(及其所关联的边),只需要在搜索到该顶点时跳过该顶点就可以了。

求关节点的算法——Tarjan算法

前面介绍的求关节点的朴素方法,需要从每个顶点出发进行DFS遍历,用邻接矩阵存储时其复杂度为O(n^3)。本节介绍的Tarjan算法只需从某个顶点出发进行一次遍历,就可以求得图中所有的关节点,因此其复杂度为O(n^2)。接下来以图8(a)所示的无向图为例介绍这种方法。

在图8(a)中,对该图从顶点4出发进行深度优先搜索,实线表示搜索前进方向,虚线表示回退方向,顶点旁的数字标明了进行深度优先搜索时各顶点的访问次序,即深度优先数。在DFS搜索过程中,可以将各顶点的深度优先数记录在数组dfn中。

图8(b)是进行DFS搜索后得到的根为顶点4的深度优先生成树。为了更加直观地描述树形结构,将此生成树改画成图8(d)所示的树形形状。在图8(d)中,还用虚线画出了两条虽然属于图G,但不属于生成树的边,即(4,5)和(6,8)。

请注意:在深度优先生成树中,如果u和v是两个顶点,且在生成树中u是v的祖先,则必有dfn[u]<dfn[v],表明u的深度优先数小于v,u先于v被访问。

图G中的边可以分为以下3种:

  1. 生成树的边,如(2,4)、(6,7)等。
  2. 回边(Back Edge):图8(d)中虚线所表示的非生成树的边,称为回边。当且仅当u在生成树中是v的祖先,或者v是u的祖先时,非生成树的边(u,v)才成为一条回边。如图8(a)及图8(d)中的(4,5)、(6,8)都是回边。
  3. 交叉边:除生成树的边、回边外,图G中的其他边称为交叉边。

请特别注意:一旦生成树确定以后,那么原图中的边只可能是回边和生成树的边,交叉边实际上是不存在的。为什么?(说明:对有向图进行DFS搜索后,非生成树的边可能是交叉边。)

假设图G中存在边(1,10),如图8(c)所示,这就是所谓的交叉边,那么顶点10(甚至其他顶点都)只能位于顶点4的左边这棵子树中。另外,如果在图G中增加两条交叉边(1,10)和(7,9),则图G就是一个重连通图,如图8(c)所示。

顶点u是关节点的充要条件如下:

  1. 如果顶点u是深度优先搜索生成树的根,则u至少有两个子女。为什么呢?因为删除u,它的子女所在的子树就断开了,不用担心这些子树之间(在原图中)可能存在边,因为交叉边是不存在的。
  2. 如果u不是生成树的根,则它至少有一个子女w,从w出发,不可能通过w、w的子孙,以及一条回边组成的路径到达u的祖先。为什么呢?这是因为如果删除顶点u及其所关联的边,则以顶点w为根的子树就从搜索树中脱离了。例如,顶点6为什么是关节点?这是因为它的一个子女顶点,如图8(d)所示,即顶点7,不存在如前所述的路径到达顶点6的祖先结点,这样,一旦顶点6删除了,则以顶点7为根结点的子树就断开了。又如,顶点7为什么不是关节点?这是因为它的所有子女顶点,当然在图8(d)中只有顶点8,存在如前所述的路径到达顶点7的祖先结点,即顶点6,这样,一旦顶点7删除了,则以顶点8为根结点的子树仍然跟图G连通。

因此,可对图G的每个顶点u定义一个low值:low[u]是从u或u的子孙出发通过回边可以到达的最低深度优先数。low[u]的定义如下:

即low[u]是取以上3项的最小值,其中:第1项为它本身的深度优先数;第2项为它的(可能有多个)子女顶点w的low[w]值的最小值,因为它的子女可以到达的最低深度优先数,则它也可以通过子女到达;第3项为它直接通过回边可以到达的最低优先数。

因此,顶点u是关节点的充要条件是:u或者是具有两个以上子女的深度优先生成树的根,或者虽然不是一个根,但它有一个子女w,使得low[w]≥dfn[u]

其中,“low[w]≥dfn[u]”的含义是:顶点u的子女顶点w,能够通过如前所述的路径到达顶点的最低深度优先数大于等于顶点u的深度优先数(注意在深度优先生成树中,顶点m是顶点n的祖先,则必有dfn[m]<dfn[n]),即w及其子孙不存在指向顶点u的祖先的回边。这时删除顶点u及其所关联的边,则以顶点w为根的子树就从搜索树中脱离了。

每个顶点的深度优先数dfn[n]值可以在搜索前进时进行统计,而low[n]值是在回退的时候进行计算的。

接下来结合图8和表1解释在回退过程中计算每个顶点n的low[n]值的方法(在表1中,当前计算出来的low[n]值用粗体、斜体及下划线标明)。

  1. 在图8(a)中,访问到顶点1后,要回退,因为顶点1没有子女顶点,所以low[1]就等于它的深度优先数dfn[1],为5。
  2. 从顶点1回退到顶点5后,要继续回退,此时计算顶点5的low值,因为顶点5可以直接通过回边(5,4)到达根结点,而根结点的深度优先数为1,所以顶点5的low值为1。
  3. 从顶点5回退到顶点3后,要继续回退,此时计算顶点3的low值,因为它的子女顶点,即顶点5的low值为1,则顶点3的low值也为1。
  4. 从顶点3回退到顶点2后,要继续回退,此时计算顶点2的low值,因为它的子女顶点,即顶点3的low值为1,则顶点2的low值也为1。
  5. 从顶点2回退到顶点4后,要继续访问它的右子树中的顶点,此时计算顶点4的low值,因为它的子女顶点,即顶点2的low值为1,则顶点4的low值也为1。

根结点4的右子树在回退过程计算顶点的low[n],方法类似。

计算出各顶点的low[n]值后,因为根结点,即顶点4有两个子女,所以顶点4是关节点;顶点5也是关节点,这是因为它的子女顶点,即顶点1的low值大于dfn[5];同样,顶点6和顶点8也是关节点。

求出关节点u后,还有一个问题需要解决:去掉该关节点u,将原来的连通图分成了几个连通分量?答案如下。

  1. 如果关节点u是根结点,则有几个子女,就分成了几个连通分量。
  2. 如果关节点u不是根结点,则有d个子女w,使得low[w]≥dfn[u],则去掉该结点,分成了d+1个连通分量。

例1 SPF结点(SPF)

题目来源:

Greater New York 2000, ZOJ1119, POJ1523

题目描述:

考虑图9中的两个网络,假定网络中的数据只在有线路直接连接的两个结点之间以点对点的方式传输。一个结点出现故障,比如图9(a)所示的网络中结点3出现故障,将会阻止其他某些结点之间的通信。结点1和结点2仍然是连通的,结点4和结点5也是连通的,但这两对结点之间的通信无法进行了。因此结点3是这个网络的一个SPF结点。

严格的定义:对于一个连通的网络,如果一个结点出现故障,将会阻止至少一对结点之间的通信,则该结点是SPF结点。

注意:图9(b)所示的网络不存在SPF结点。至少两个结点出现故障后,才会使得其他某对结点之间无法通信。

输入描述:

输入文件包含多个测试数据,每个测试数据描绘了一个网络。每个网络的数据包含多对整数,每对整数占一行,表示两个直接连接的结点。结点对中两个结点的顺序是无关的,1 2和2 1表示同一对连接。结点序号范围为1~1000,每个网络的数据中最后一行为一个0,表示该网络数据的结束。整个输入文件最后一行为一个0,代表输入结束。读入时需要忽略输入文件中的空行。

输出描述:

对输入文件中的每个网络,首先输出该网络在输入文件中的序号,然后是该网络中的SPF结点。具体格式为:第1个网络的序号为"Network #1";第2个网络的序号为"Network #2",等等。对网络中的每个SPF结点,输出占一行,输出格式如样例输出所示,输出信息标明SPF结点的序号及该SPF结点出现故障后将整个网络分成几个连通的子网络。如果网络中不存在SPF结点,则只输出"No SPF nodes"。每两个网络的输出之间,输出一个空行。

在用程序实现前面所述的求关节点的算法时,需要解决以下几个问题。

  1. 如何判断顶点v是顶点u的祖先结点。
  2. 如何判断边(v,u)是回边。
  3. 如何判断顶点v是顶点u的儿子结点。

这3个问题都是在深度优先搜索函数dfs中解决的。从顶点u出发进行DFS搜索时,要判断其他每个顶点v是否跟u是否邻接、是否未访问过。如果v跟u邻接,则在生成树中就是两种情况。

  1. 如果顶点v是顶点u的邻接顶点,且此时v还未访问过,则v是u的儿子结点。
  2. 如果顶点v是顶点u的邻接顶点,且此时v已经访问过了,则v是u的祖先结点,且(v,u)就是一条回边。

在下面的代码中,求每个顶点的low[]值的代码特别地用边框标明了,从中可以看出,每次从顶点u的某一个邻接顶点回退到顶点u时,计算顶点u的low[]值;当顶点u的所有邻接顶点都访问完毕,顶点u的low[]值才计算完毕。

代码如下:


重连通分量的求解

在求关节点的过程中就能顺便把每个重连通分量求出。方法是:建立一个栈,存储当前重连通分量,在DFS过程中,每找到一条生成树的边或回边,就把这条边加入栈中。如果遇到某个顶点u的子女顶点v满足dfn[u]≤low[v],说明u是一个割点,同时把边从栈顶一条条取出,直到遇到了边(u,v),取出的这些边与其关联的顶点,组成一个重连通分量。割点可以属于多个重连通分量,其余顶点和每条边属于且只属于一个重连通分量。

以上方法具体实现详见下面的例2。

例2 输出无向连通图各个连通分量

输入描述。输入文件中包含多个测试数据,每个测试数据的格式为:第1行为两个整数n和m,分别表示顶点个数和边数,然后有m行,