ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【图论】—— 有向图的强连通分量 [打印本页]

作者: 吴旭华 时间: 2022-6-25 21:29
标题: 【图论】—— 有向图的强连通分量

给定有向图 $G=(V,E)$ ，若存在 $r \epsilon V$ ，满足从 $r$ 出发能到达 $V$ 中所有的点，则称 $G$ 是一个“流图”（ Flow Graph ），记为 $(G,r)$ ，其中， $r$ 称为流图的源点。
在一个流图 $(G,r)$ 上从 $r$ 进行深度优先遍历，每个点只访问一次。所有发生递归的边 $(x,y)$ （换言之，从 $x$ 到 $y$ 是对 $y$ 的第一次访问）构成一棵以 $r$ 为根的树，我们把它称为流图 $(G,r)$ 的搜索树。
同时，在深度优先遍历的过程中，按照每一个节点第一次被访问的时间顺序，依次给予流图中 N 个节点 1~N 的整数标记，称为时间戳，记为 $dfn[x]$ 。
流图中的每条有向边 $(x,y)$ 必然是以下四种之一：

树枝边，指搜索树中的边，即 $x$ 是 $y$ 的父节点
前向边，指搜索树中 $x$ 是 $y$ 的祖宗节点
后向边，指搜索树中 $y$ 是 $x$ 的祖宗节点
横叉边，指除了以上三种情况之外的边，它一定满足 $dfn[y] < dfn[x]$

如下图“流图”以及其搜索树所示：
加粗的表示的是树枝边，并构成一棵搜索树。

有向图的强连通分量

  给定一张有向图。若对于图中的任意两个结点 $x,y$ ，既存在从 $x$ 到 $y$ 的路径，也存在从 $y$ 到 $x$ 的路径，则称该有向图是“强连通图”。

  有向图的极大连通子图称为“强连通分量”，简记为 SCC(Strongly Connected Component)。
  此处的“极大”的含义和双连通分量的“极大”的含义类似。
  Tarjan算法基于有向图的深度优先遍历，能够在线性的时间里求出一张有向图的强连通分量。
一个“环”一定是强连通图。如果既存在从 $x$ 到 $y$ 的路径，也存在从 $y$ 到 $x$ 的路径，那么 $x,y$ 显然在一个环中。因此，Tarjan算法的基本思路就是对每个点，尽量找到与它一起能够构成环的所有节点。
容易发现，“前向边” $(x,y)$ 没有什么用处，因为搜索树上本来就存在从 $x$ 到 $y$ 的路径。
“后向边” $(x,y)$ 非常有用，因为它可以从搜索树上从 $y$ 到 $x$ 的路径一起构成环。
“横向边” $(x,y)$ 视情况而定，如果从 $y$ 出发能够找到一条回到 $x$ 的祖宗节点，那么 $(x,y)$ 就是有用的。

为了找到通过“后向边”和“横叉边”构成的换，Tarjan算法在深度优先遍历的同时维护一个栈。
当访问到结点 x 时，栈中需要保存以下两类节点：

搜索树上 x 的祖宗节点，记为集合 $anc(x)$

设 $y\epsilon anc(x)$ 。若存在后向边 $(x,y)$ ，则 $(x,y)$ 与 y 到 x 的路径一起形成环。
已经访问过，并且存在一条路径到达 $anc(x)$ 的节点

设 z 是一个这样的点，从 z 出发存在一条路径到达 $y\epsilon anc(x)$ 。若存在横叉边 $(x,z)$ ，则 $(x,z)$ 、z 到 y 的路径、y 到 x 的路径构成一个环。

综上所述，栈中的节点就是能与从 x 出发的“后向边”和“横叉边”形成环的节点。进而可以引入“追溯值”的概念。

追溯值

设 $subtree(x)$ 表示流图的搜索树中以 x 为根的子树。x 的追溯值 $low(x)$ 定义为满足以下条件的节点的最小时间戳：

该点在栈中
存在一条从 $subtree(x)$ 出发的有向边，以该点为终点

根据定义，Tarjan算法按照以下步骤计算“追溯值”：

当节点 x 第一次被访问时，把 x 入栈，初始化 $low[x] = dfn[x]$
扫描从 x 出发的每一条边 $(x,y)$
- 若 y 没有被访问过，则说明 $(x,y)$ 是“树枝边”，递归访问 y ，从 y 回溯后，令 $low[x]=min(low[x],low[y])$
- 若 y 被访问过且 y 在栈中，则令 $low[x] = min(low[x],dfn[y])$
从 x 回溯之前，判断是否有 $low[x]=dfn[x]$ 。若成立，则不断从栈中弹出节点，直至 x 出栈

下页图中的中括号【】里的数值标注了每个节点的的“追溯值” $low$

强连通分量判定法则

在追溯值的计算过程中，若从 x 回溯前，有 $low[x] = dfn[x]$ 成立，则栈中从 x 到栈顶的所有节点构成一个强连通分量。
大致来说，在计算追溯值的第三步，如果 $low[x] = dfn[x]$ ，那么说明 $subtree(x)$ 中的节点不能与栈中其他结点一起构成环。另外，因为横叉边的终点时间必然小于起点时间戳，所以 $subtree(x)$ 中的结点也不可能直接到达尚未访问的结点（时间戳更大）。综上所述，栈中从 x 到栈顶的所有节点不能与其他结点构成环。
由因为我们及时进行了判定和出栈操作，所以从 x 到栈顶的所有节点独立构成一个强连通分量。
Tarjan算法模板

void tarjan(int u)
{
dfn[u] = low[u] = timestamp;
stk[++ top] = u, in_stk[u] = true;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if(in_stk[j])
low[u] = min(low[u], dfn[j])
}
if(dfn[u] == low[u])
{
int y;
++ scc_cnt;
do{
y = stk[top ++ ];
in_stk[y] = false;
id[y] = scc_cnt;
}while(y != u)
}
}

复制代码

缩点

我们可以把每一个 SCC 缩成一个点。对于原图中的每条有向边 $(x,y)$ 若 $id[x]\neq id[y]$ ，则在编号为 $id[x]$ 与编号为 $id[y]$ 的SCC之间连边。
最终，我们会得到一个有向无环图（DAG）
[code]for(int x = 1; x

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)