Tarjan算法学习笔记

目录

无向图的割点与桥

时间戳：

搜索树：

追溯值：

割边判定法则：

割点判定法则：

无向图的双连通分量

定理：

边双连通分量(e-DCC)的求法：

e-DCC的缩点：

有向图的连通性

追溯值：

Tarjan算法求强连通分量（SCC）:

---

无向图的割点与桥

无向连通图G=(V,E):

若对于 x 属于 V，从图中删去节点 x 以及所有与 x 关联的边之后，G 分裂成两个或两个以上不相连的子图，则称 x 为 G 的割点。

若对于 e 属于 E ，从图中删去边 e 之后，G 分裂成两个不相连的子图，则称 e 为 G 的桥或割边。

一般无向图（不一定连通）的“割点”和“桥”就是它的各个连通块恶的“割点”和“桥”。

Tarjan算法能够求出有向图的强连通分量、必经点与必经边。Tarjan算法是基于无向图的深度优先遍历。

时间戳：

在图的深度优先遍历过程中，按照每个节点第一次被访问的时间顺序，依次给与 N 个节点 1~N 的整数标记，给标记称为“时间戳”,记为 dfn[n]。

搜索树：

在无向连通图中任选一个节点出发进行深度优先遍历，每个点只访问一次。所有发生递归的边（x，y）（换言之，从x到y是对y的第一次访问）构成一棵树，我们把它称为“无向连通图的搜索树”。当然，一般无向图（不一定连通）的各个连通块的搜索树构成无向图的“搜索森林”。

追溯值：

 设 subtree[x] 表示搜索树中以 x 为根的子树。low[x] 定义为以下节点的时间戳的最小值。

1）subtree[x] 中的节点。

2）通过1条不在搜索树上的边，能够到达 subtree[x] 的节点。

根据定义，为了计算 low[x],应该先令 low[x]=dfn[x],然后考虑从 x 出发的每条边。

若在搜索树上 x 是 y 的父节点，则令 low[x]=min(low[x],low[y]).

若无向边（x，y）不是搜索树上的边，则令 low[x]=min(low[x],dfn[y]).

割边判定法则：

无向边（x，y）是桥，当且仅当搜索树上存在 x 的一个子节点 y ，满足：dfn[x]<low[y].

根据定义，dfn[x]<low[y] 说明从 subtree[y] 出发，在不经过 （x，y）的前提下，不管走那条边，都无法到达 x 或比 x 更早访问的节点。若把（x，y）删除，则 subtree[y] 就好像形成了一个封闭的环境，与节点 x 没有边相连，图断开成了两部分，因此（x，y）是割边。

反之，若不存在这样的子节点 y ，使得 dfn[x]<low[y],则说明每个 subtree[y] 都能绕行其他边到达 x 或比 x 更早访问的节点，（x，y）自然就不是割边。

桥一定是搜索树中的边，并且一个简单环中的边一定都不是桥。

特别需要注意, 因为我们遍历的是无向图，所以从每个点 x 出发，总能访问到它的父节点 fa。 根据 low 的计算方法，(x,fa) 属于搜索树上的边，且 fa 不是 x 的子节点，故不能用 fa 的时间戳来更新low[x] 。
但是，如果仅记录每个节点的父节点，会无法处理重边的情况——当 x 与 fa 之间有多条边时，(x,fa) 一定不是桥。 在这些重复的边中, 只有一条算是“搜索树上的边” 其他的几条都不算。 故有重边时, dfn[fa] 能用来更新 low[x]。
一个好的解决方案是:改为记录“递归进入每个节点的边的编号” 。编号可认为是边在邻接表中存储的下标位置。 这里介绍“成对变换”技巧。把无向图的每一条边看作双向边, 成对存储在下标 “2和3” “4和5” “6和7”处。若沿着编号为的边递归进入了节点 x ，则忽略从 x 出发的编号为 i xor 1 的边，通过其他边计算 low[x] 即可。

割点判定法则：

若 x 不是搜索树的根节点(深度优先遍历的起点)，则 x 是割点当且仅当搜索树上存在 x 的一个子节点 y，满足:dfn[x] <= low[y]
特别地，若 x 是搜索树的根节点，则 x 是割点当且仅当搜索树上存在至少两个子节点 y1，y2 满足上述条件。
证明方法与割边的情形类似，这里就不再赞述。
因为割点判定法则是小于等于号，所以在求割点时, 不必考虑父节点和重边的问题，从X出发能访问到的所有点的时间戳都可以用来更新 low[x] 。

无向图的双连通分量

若一张无向连通图不存在割点，则称它为“点双连通图”。若一张无向连通图不存在桥，则称它为“边双连通图”。
无向图的极大点双连通子图被称为“点双连通分量”，简记为“v-DCC”。无向连通图的极大边双连通子图被称为“边双连通分量”，简记为“e-DCC”。 二者统称为“双连通分量”，简记为“DCC”。
在上面的定义中，我们称一个双连通子图 G'=(V',E'）“极大” (其中 V' 属于 V , E' 属于 E )，是指不存在包含 G' 的更大的子图 G"=(V",E")，满足 V' 属于V＂属于 V，E' 属于 P" 属于 E 并且 G" 也是双连通子图。

定理：

一张无向连通图是“点双连通图” ，当且仅当满足下列两个条件之一。
1）.图的顶点数不超过2。
2）.图中任意两点都同时包含在至少一个简单环中。其中“简单环”指的是不自交的环，也就是我们通常画出的环。
一张无向连通图是“边双连通图” ，当且仅当任意一条边都包含在至少一个简单环中。
证明：
该定理给出了无向连通图是“点双连通图”或“边双连通图”的充要条件。我们以“点双连通图”为例进行证明，“边双连通图”的证明类似。
对于顶点数不超过2的情况， 定理显然成立, 下面假设图中顶点数不小于3。先证充分性。若任意两点 x, y 都同时包含在至少一个简单环中，则 x，y 之间至少有两条不相交的路径。无论从图中删除哪个节点，x,y 均能通过两条路径之一相连。故图中不存在割点，是点双连通图。
再证必要性。反证法，假设一张无向连通图是“点双连通图” 并且存在两点 x，y，它们不同时处于任何一个简单环中。

如果 x，y 之间仅存在1条简单路径，那么路径上至少有一个割点，与“点双连通”矛盾。

如果 x，y 之间存在2条或2条以上的简单路径，那么容易发现，任意两条都至少有一个除x，y之外的交点:进一步可推导出, x,y之间的所有路径必定同时交于除 x，y 之外的某一点 p (不然就会存在两条没有交点的路径，形成一个简单环）
根据定义，p是一个割点，与“点双连通”矛盾。故假设不成立。证毕。

边双连通分量(e-DCC)的求法：

边双连通分量的计算非常容易。只需求出无向图中所有的桥，把桥都删除后，无向图会分成若干个连通块，每一个连通块就是一个“边双连通分量”。

在具体的程序实现中, 一般先用Tarjan算法标记出所有的桥边。然后，再对整个无向图执行一次深度优先遍历(遍历的过程中不访问桥边），划分出每个连通块。下面的代码在Taran求桥的参考程序基础上，计算出数组c，c[X]表示节点 x 所属的“边双连通分量”的编号。

e-DCC的缩点：

缩点：将一个强连通分量缩成一个点。

把每个 e-DCC 看作一个节点，把桥边 (x,y) 看作连接编号为 c[x] 和 c[y] 的 e-DCC 对应节点的无向边，会产生一棵树（若原来的无向图不连，则产生森林)。这种把 e-DCC 收缩为一个节点的方法就称为“缩点”。下面的代码在Tarjan求桥、求e-DCC的参考程序基础上，把e-DCC缩点，构成一棵新的树(或森林)，存储在另一个邻接表中。

有向图的连通性

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

1）.树枝边，指搜索树中的边，即x是y的父节点（一种特殊的前向边）。
2）.前向边，指搜索树中x是y的祖先节点。
3）.后向边，指搜索树中y是x的祖先节点。
4）.横叉边，指除了以上三种情况之外的边，它一定满足 dfn[y]<dfn[x] .

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

有向图的极大强连通子图被称为“强连通分量” 简记为SCC。 此处“极大”的含义与双连通分量“极大”的含义类似。

Tarjan 算法基于有向图的深度优先遍历，能够在线性时间内求出一张有向图的各个强连通分量。
一个“环” 一定是强连通图。如果既存在从x到y的路径，也存在从y到的那么x,y显然在一个环中。因此，Tarjan算法的基本思路就是对于每个点，尽找到与它一起能构成环的所有节点。

容易发现，前向边”(x,y)没有什么用处，因为搜索树上本来就存在从x到y。“后向边” (x,y) 非常有用，因为它可以和搜索树上从y到x的路径一起构成环。“横叉边” (x,y) 视情况而定，如果从y出发能找到一条路径回到x的祖先节点，那么(x,y)就是有用的。

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

1）.搜索树上x的祖先节点，记为集合 anc(x)。
设y属于anc(x)。 若存在后向边(x,y)，则(x,y) 与y到x的路径一起形成环。

2）.已经访问过, 并且存在一条路径到达 anc(x) 的节点。
设z是一个这样的点，从出发存在一条路径到达y属于anc(x)。 若存在横叉边(x,2), 则(x,z)、z到y的路径、y到x的路径形成一个环。

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

追溯值：

设 subtree(x) 表示流图的搜索树中以x为根的子树。x的追溯值low[x]定义为满足以下条件的节点的最小时间戳。
1）.该点在栈中。
2）.存在一条从 subtree(x) 出发的有向边, 以该点为终点。

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

1.当节点x第一次被访问时，把x入栈， 初始化low[x]=dfn[x]。

2.扫描从 x出发的每条边(x,y)。

        (1)若y没被访问过，则说明(x,y）是树枝边，递归访问y，从回潮之后,
        令low[x]=min(low[xl,lowly)。
        (2)若y 被访问过并且y在栈中，则令lowlx]= min(lowlxl.dfnly).
3.从x回溯之前，判断是否有lowlx]=dfn[x]。若成立，则不断从栈中弹出节点，直至x出栈。

__________________________________________________________________________

1）.树枝边，指搜索树中的边，即x是y的父节点（一种特殊的前向边）。
2）.前向边，指搜索树中x是y的祖先节点。
3）.后向边，指搜索树中y是x的祖先节点。
4）.横叉边，指除了以上三种情况之外的边，它一定满足 dfn[y]<dfn[x] .

如何判断某一点是否在某个强连通分量内：

情况一：存在后向边指向祖先节点。

情况二：先走到横叉边，横叉边再走到祖先节点。

Tarjan算法求强连通分量（SCC）:

对每个点定义两个时间戳

dfn[u]表示遍历到u的时间戳

low[u]从u开始走，所能遍历到的最小时间戳是什么

u是其所在的强连通分量的最高点，等价于dfn[u]==low[u]