连通性相关算法
有向图的强连通分量
强连通的定义是:有向图 G 强连通是指,G 中任意两个结点连通。
强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连通子图。
这里要介绍的是如何来求强连通分量。
DFS 生成树
在介绍该算法之前,先来了解 DFS 生成树,我们以下面的有向图为例:
有向图的 DFS 生成树主要有 4 种边(不一定全部出现):
- 树边(tree edge):示意图中以黑色边表示,每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
- 反祖边(back edge):示意图中以红色边表示(即
),也被叫做回边,即指向祖先结点的边。 - 横叉边(cross edge):示意图中以蓝色边表示(即
),它主要是在搜索的时候遇到了一个已经访问过的结点,但是这个结点 并不是 当前结点的祖先。 - 前向边(forward edge):示意图中以绿色边表示(即
),它是在搜索的时候遇到子树中的结点的时候形成的。
我们考虑 DFS 生成树与强连通分量之间的关系。
如果结点
反证法:假设有个结点
tarjan算法求强连通分量
在 Tarjan 算法中为每个结点
:深度优先搜索遍历时结点 被搜索的次序。 :在 的子树中能够回溯到的最早的已经在栈中的结点。设以 为根的子树为 。 定义为以下结点的 的最小值: 中的结点;从 通过一条不在搜索树上的边能到达的结点。
一个结点的子树内结点的 dfn 都大于该结点的 dfn。
从根开始的一条路径上的 dfn 严格递增,low 严格非降。
按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索,维护每个结点的 dfn
与 low
变量,且让搜索到的结点入栈。每当找到一个强连通元素,就按照该元素包含结点数目让栈中元素出栈。在搜索过程中,对于结点
未被访问:继续对 进行深度搜索。在回溯过程中,用 更新 。因为存在从 到 的直接路径,所以 能够回溯到的已经在栈中的结点, 也一定能够回溯到。 被访问过,已经在栈中:根据 low 值的定义,用 更新 。 被访问过,已不在栈中:说明 已搜索完毕,其所在连通分量已被处理,所以不用对其做操作。
代码模板
1 |
|
习题
- [P2341 USACO03FALL / HAOI2006] 受欢迎的牛 G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 1236 – Network of Schools (poj.org)
- [P2272 ZJOI2007] 最大半连通子图 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
无向图的双连通分量
割点和桥的定义
在一张连通的无向图中,对于两个点
在一张连通的无向图中,对于两个点
边双连通具有传递性,即,若
点双连通 不 具有传递性,反例如下图,
割点
对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)。
比如说,下面图中,点2就是割点
割边
和割点差不多,叫做桥。
对于一个无向图,如果删掉一条边后图中的连通分量数增加了,则称这条边为桥或者割边。严谨来说,就是:假设有连通图
, 是其中一条边(即 ),如果 是不连通的,则边 是图 的一条割边(桥)。
比如说,下图中,
红色的边就是割边。
DFS 找桥并判断边双连通
首先,对原图进行 DFS。
如上图所示,黑色与绿色边为树边,红色边为非树边(可能为返祖边和横叉边)。每一条非树边连接的两个点都对应了树上的一条简单路径,我们说这条非树边 覆盖 了这条树上路径上所有的边。绿色的树边 至少 被一条非树边覆盖,黑色的树边不被 任何 非树边覆盖。
我们如何判断一条边是不是桥呢?显然,非树边和绿色的树边一定不是桥,黑色的树边一定是桥。
不难发现,对于红色边所在的环,其中的点的low值都小于等于环上最高的点,因为他们都能通过红色边回到环上的最高点。
而对于图中黑色的边,其父节点的dfn值一定小于子节点的low值,反证法:记当前边的编号为a,父亲节点的编号为f,子节点的编号为s,如果子节点的low值小于等于父亲节点的dfn值,那么从子节点出发,一定有一条不经过边a的简单路径,使得除了a以外,还有一条简单路径连接能够连接f和s,根据定义,边a不是桥。
所以,只需要在dfs的时候判断一下dfn[u] < low[j]
即可确定一个桥
用以上的方法
tarjan算法求桥模板
1 |
|
DFS 找割点并判断点双连通
如果我们尝试删除每个点,并且判断这个图的连通性,那么复杂度会特别的高。所以要介绍一个常用的算法:Tarjan。
首先,我们上一个图:
很容易的看出割点是 2,而且这个图仅有这一个割点。
首先,我们按照 DFS 序给他打上时间戳(访问的顺序)。
这些信息被我们保存在一个叫做 dfn
的数组中。
还需要另外一个数组 low
,用它来存储不经过其父亲能到达的最小的时间戳。
例如 low[2]
的话是 1,low[5]
和 low[6]
是 3。
然后我们开始 DFS,我们判断某个点是否是割点的根据是:对于某个顶点
此根据惟独不适用于搜索的起始点,其需要特殊考虑:若该点不是割点,则其他路径亦能到达全部结点,因此从起始点只「向下搜了一次」,即在搜索树内仅有一个子结点。如果在搜索树内有两个及以上的儿子,那么他一定是割点了(设想上图从 2 开始搜索,搜索树内应有两个子结点:3 或 4 及 5 或 6)。如果只有一个儿子,那么把它删掉,不会有任何的影响。比如下面这个图,此处形成了一个环。
我们在访问 1 的儿子时候,假设先 DFS 到了 2,然后标记用过,然后递归往下,来到了 4,4 又来到了 3,当递归回溯的时候,会发现 3 已经被访问过了,所以不是割点。
更新 low
的伪代码如下:
1 |
|
总结性的说,我们在执行tarjan算法的时候,对于一条边{x, y},当low[y] >= dfn[x]
时
- 如果x不是根节点,那么x是割点
- 如果x是根节点,当至少存在两个子节点y,有low[y] >= dfn[x]时,x是割点,否则不是割点
tarjan找割点模板
1 |
|
点双连通分量缩点
- 每个割点单独作为一个点
- 从每个v-dcc向其他所包含的每个割点连边
习题
一些有用的结论
把一个图变成强连通:需要加边数量为:max{q,p}, 其中p,q分别为缩点后,入度为0的的点数量和出度为0的点数量
把一个图变成双联通:需要加边数量为: