目录
- 【基本概念】
-
- 1.连通图与连通分量
- 2.无向图的割点与桥
- 【Tarjan求桥】
-
- 1.算法思想
- 2.模板
- 【Tarjan求割点】
-
- 1.算法思想
- 2.模板
- 【参考资料】
【基本概念】
1.连通图与连通分量
- 连通图：无向图 G G G 中，若对任意两点，从顶点 V i V_i Vi 到顶点 V j V_j Vj 有路径，则称 V i V_i Vi 和 V j V_j Vj 是连通的，图 G G G 是一连通图。
- 连通分量：无向图 G G G 的连通子图称为 G G G 的连通分量。
-
任何连通图的连通分量只有一个，即其自身，而非连通的无向图有多个连通分量。
以下图为例，总共有四个连通分量，分别是： A B C D ABCD ABCD、 E E E、 F G FG FG、 H I HI HI。
2.无向图的割点与桥
给定无向连通图 G = ( V , E ) G=(V,E) G=(V,E)：
-
若对于 x ∈ V x∈V x∈V，从图中删去节点 x x x 以及所有与 x x x 关联的边之后， G G G 分裂成两个或两个以上不相连的子图，则称 x x x 为 G G G 的割点。
如下图，若去掉 0 0 0，则图被分成 12 12 12 和 34 34 34 两个连通分量；若去掉 3 3 3，则图被分成 012 012 012 和 4 4 4 两个连通分量。故： 0 、 3 0、3 0、3 是割点，两者是一个割点集，点连通度（最小割点集合点数）是 2 2 2。
-
若对于 e ∈ E e∈E e∈E，从图中删去边 e e e 之后， G G G 分裂成两个不相连的子图，则称 e e e 为 G G G 的桥或割边。
如下图，去掉 5 − 6 5-6 5−6， 2 − 5 2-5 2−5 后不再连通，图被分为 1234 、 5 、 6 1234、5、6 1234、5、6三个连通分量。故： 5 − 6 、 2 − 5 5-6、2-5 5−6、2−5 是割边，两者组成的集是割边集，边连通度（最小割边集合边数）是 2 2 2。
一般无向图 （不一定连通）的割点和桥就是它的各个连通块的割点和桥。
【Tarjan求桥】
1.算法思想
时间戳
在图的深度优先遍历过程中，按照每个节点第一次被访问的时间顺序，依次给予 N N N 个节点 1 ∼ N 1 \sim N 1∼N 的整数标记，该标记就被称为时间戳，记为 d f n [ x ] dfn[x] dfn[x]。
搜索树
在无向连通图中任选一个节点出发进行深度优先遍历，每个点只访问一次。
所有发生递归的边 ( x , y ) (x,y) (x,y)（换言之，从 x x x 到 y y y 是对 y y y 的第一次访问）构成一棵树，我们把它称为无向连通图的搜索树。
当然，一般无向图（不一定连通）的各个连通块的搜索树构成无向图的搜索森林。
追溯值
除了时间戳之外，Tarjan算法还引入了一个追溯值 l o w [ x ] low[x] low[x]。
设 s u b t r e e ( x ) subtree(x) subtree(x) 表示搜索树中以 x x x 为根的子树。 l o w [ x ] low[x] low[x] 定义为以下节点的时间戳的最小值：
- s u b t r e e ( x ) subtree(x) subtree(x) 中的节点。
- 通过 1 1 1 条不在搜索树上的边，能够到达 s u b t r e e ( x ) subtree(x) subtree(x) 的节点。
根据定义，为了计算 l o w [ x ] low[x] low[x]，应该先令 l o w [ x ] = d f n [ x ] low[x] = dfn[x] low[x]=dfn[x]，然后考虑从 x x x 出发的每条边 ( x , y ) (x,y) (x,y)：
- 若在搜索树上 x x x 是 y y y 的父节点，则令 l o w [ x ] = m i n ( l o w [ x ] , l o w [ y ] ) low[x] = min(low[x], low[y]) low[x]=min(low[x],low[y])。
- 若无向边 ( x , y ) (x, y) (x,y) 不是搜索树上的边，则令 l o w [ x ] = m i n ( l o w [ x ] , d f n [ y ] ) low[x] = min(low[x], dfn[y]) low[x]=min(low[x],dfn[y])。
割边判定法则
无向边 ( x , y ) (x, y) (x,y) 是桥，当且仅当搜索树上存在 x x x 的一个子节点 y y y，满足：
d f n [ x ] < l o w [ y ] dfn[x] < low[y] dfn[x]<low[y]
简单证明：
根据定义， d f n [ x ] < l o w [ y ] dfn[x] < low[y] dfn[x]<low[y] 说明从 s u b t r e e ( y ) subtree(y) subtree(y) 出发，在不经过 ( x , y ) (x,y) (x,y) 的前提下，不管走哪条边，都无法到达 x x x 或比 x x x 更早访问的节点。若把 ( x , y ) (x, y) (x,y) 删除，则 s u b t r e e ( y ) subtree(y) subtree(y) 就好像形成了一个封闭的环境，与节点 x x x 没有边相连，图断开成了两部分，因此 ( x , y ) (x,y) (x,y) 是割边。
反之，若不存在这样的子节点 y y y，使得 d f n [ x ] < l o w [ y ] dfn[x] < low[y] dfn[x]<low[y]，则说明每个 s u b t r e e ( y ) subtree(y) subtree(y) 都能绕行其他边到达 x x x 或比 x x x 更早访问的节点， ( x , y ) (x,y) (x,y) 自然就不是割边。
桥一定是搜索树中的边，并且一个简单环中的边一定都不是桥。
2.模板
特别需要注意，因为我们遍历的是无向图，所以从每个点 x x x 出发，总能访问到它的父节点 f a fa fa。根据 l o w low low 的计算方法， ( x , f a ) (x,fa) (x,fa) 属于搜索树上的边，且 f a fa fa 不是 x x x 的子节点，故不能用 f a fa fa 的时间戳来更新 l o w [ x ] low[x] low[x]。
但是，如果仅记录每个节点的父节点，会无法处理重边的情况——当 x x x 与 f a fa fa 之间有多条边时， ( x , f a ) (x,fa) (x,fa) 一定不是桥。
一个好的解决方案是：改为记录递归进入每个节点的边的编号。编号可认为是边在邻接表中存储的下标位置。利用成对变换技巧，把无向图的每条边看作双向边，成对存储在下标"2和3" “4和5” “6和7”…处。若沿着编号为 i i i 的边递归进入了节点 x x x，则忽略从 x x x 出发的编号为 i x o r 1 i\ xor\ 1 i xor 1 的边，通过其他边计算 l o w [ x ] low[x] low[x] 即可。
const int N = 100010;
int head[N], ver[N * 2], Next[N * 2];
int dfn[N], low[N], n, m, tot, num;
bool bridge[N * 2];
void add(int x, int y)
{
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void tarjan(int x, int in_edge)
{
dfn[x] = low[x] = ++num;
for(int i = head[x]; i; i = Next[i])
{
int y = ver[i];
if(!dfn[y])
{
tarjan(y, i);
low[x] = min(low[x], low[y]);
if(low[y] > dfn[x])
bridge[i] = bridge[i ^ 1] = true;
}
else if(i != (in_edge ^ 1))
low[x] = min(low[x], dfn[y]);
}
}
int main()
{
cin >> n >> m;
tot = 1;
for(int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
for(int i = 1; i <= n; i++)
if(!dfn[i])
tarjan(i, 0);
for(int i = 2; i < tot; i += 2)
if(bridge[i])
printf("%d %d\n", ver[i ^ 1], ver[i]);
}
【Tarjan求割点】
1.算法思想
割点判定法则
若 x x x 不是搜索树的根节点（深度优先遍历的起点），则 x x x 是割点当且仅当搜索树上存在 x x x 的一个子节点 y y y，满足：
d f n [ x ] ≤ l o w [ y ] dfn[x]≤low[y] dfn[x]≤low[y]
特别地，若 x x x 是搜索树的根节点，则 x x x 是割点当且仅当搜索树上存在至少两个子节点 y 1 , y 2 y_1,y_2 y1,y2 满足上述条件。
证明方法与割边的情形类似，这里就不再赘述。
2.模板
因为割点判定法则是小于等于号，所以在求割点时，不必考虑父节点和重边的问题，从 x x x 出发能访问到的所有点的时间戳都可以用来更新 l o w [ x ] low[x] low[x]。
下面的程序求出一张无向图中所有的割点。
const int SIZE = 100010;
int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
int dfn[SIZE], low[SIZE], stack[SIZE];
int n, m, tot, num, root;
bool cut[SIZE];
void add(int x, int y)
{
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void tarjan(int x)
{
dfn[x] = low[x] = ++num;
int flag = 0;
for(int i = head[x]; i; i = Next[i])
{
int y = ver[i];
if(!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
if(low[y] >= dfn[x])
{
flag++;
if(x != root || flag > 1) cut[x] = true;
}
}
else
low[x] = min(low[x], dfn[y]);
}
}
int main()
{
cin >> n >> m;
tot = 1;
for(int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
if(x == y) continue;
add(x, y), add(y, x);
}
for(int i = 1; i <= n; i++)
if(!dfn[i])
root = i, tarjan(i);
for(int i = 1; i <= n; i++)
if(cut[i])
printf("%d ", i);
puts("are cut-vertexes");
}
【参考资料】
- 《算法竞赛进阶指南》
- 图的连通性