临街小站

tarjan强连通分量

引入

在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。

下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。

tarjan是一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。

Tip

  • DFN(n)为节点n搜索的次序编号(时间戳),Low(n)为n或n的子树能够追溯到的最早的栈中节点的次序号。
  • Low数组是一个标记数组,记录该点所在的强连通子图所在搜索子树的根节点的DFN值

  • 当DFN(n)=Low(n)时,栈里n以及n以上的顶点全部出栈,且刚刚出栈的就是一个极大强连通分量。

算法演示

  1. 从节点1开始DFS,把遍历到的节点加入栈中。搜索到节点u=6时,DFN[6]=LOW[6],找到了一个强连通分量。退栈到u=v为止,{6}为一个强连通分量。

  1. 返回节点5,发现DFN[5]=LOW[5],退栈后{5}为一个强连通分量。

  1. 返回节点3,继续搜索到节点4,把4加入堆栈。发现节点4向节点1有后向边,节点1还在栈中,所以LOW[4]=1。节点6已经出栈,(4,6)是横叉边,返回3,(3,4)为树枝边,所以LOW[3]=LOW[4]=1。

  1. 继续回到节点1,最后访问节点2。访问边(2,4),4还在栈中,所以LOW[2]=DFN[4]=5。返回1后,发现DFN[1]=LOW[1],把栈中节点全部取出,组成一个连通分量{1,3,4,2}。

以上,求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。

运行Tarjan算法的过程中,每个顶点都被访问了一次,且只进出了一次堆栈,每条边也只被访问了一次,所以该算法的时间复杂度为O(N+M)。

Low[i]表示i所能直接或间接达到时间最小的顶点。(实际操作中Low[i]不一定最小,但不会影响程序的最终结果)

详解

  • 数组的初始化:当首次搜索到点p时,DFN与Low数组的值都为到该点的时间。

  • 堆栈:每搜索到一个点,将它压入栈顶。

  • 当点p有与点p’相连时,如果此时(时间为dnf[p]时)p’还未访问过,p的low值为两点的low值中较小的一个。

  • 当点p有与点p’相连时,如果此时(时间为dfn[p]时)p’在栈中,p的low值为p的low值和p’的dfn值中较小的一个。

  • 每当搜索到一个点经过以上操作后(也就是子树已经全部遍历)的low值等于dfn值,则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。

  • 继续搜索(或许会更换搜索的起点,因为整个有向图可能分为两个不连通的部分),直到所有点被遍历。

支撑

  1. Tarjan算法基于定理:在任何深度优先搜索中,同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说,强连通分量一定是有向图的某个深搜树子树。

  2. 可以证明,当一个点既是强连通子图Ⅰ中的点,又是强连通子图Ⅱ中的点,则它是强连通子图Ⅰ∪Ⅱ中的点。

  3. low值记录该点所在强连通子图对应的搜索子树的根节点的Dfn值。该子树中的元素在栈中一定是相邻的,且根节点在栈中一定位于所有子树元素的最下方。

  4. 强连通分量由若干个环组成的。所以,当有环形成时(也就是搜索的下一个点已在栈中),我们将这一条路径的low值统一,即这条路径上的点属于同一个强连通分量。

  5. 如果遍历完整个搜索树后某个点的dfn值等于low值,则它是该搜索子树的根。这时,它以上(包括它自己)一直到栈顶的所有元素组成一个强连通分量。

实现

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
tarjan(u)
{
DFN[u]=Low[u]=++Index//为节点u设定次序编号和Low初值
Stack.push(u)//将节点u压入栈中
for each(u,v) in E//枚举每一条边
if (v is not visted)//如果节点v未被访问过
tarjan(v)//继续向下找
Low[u]=min(Low[u],Low[v])
else if (v in S)//如果节点v还在栈内
Low[u]=min(Low[u],DFN[v])
if (DFN[u]==Low[u])//如果节点u是强连通分量的根
repeat{
v=S.pop//将v退栈,为该强连通分量中一个顶点
print v
until(u==v)
}

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define M 9999//题目中可能的最大点数
int STACK[M],top=0;//Tarjan算法中的栈
bool InStack[M];//检查是否在栈中
int DFN[M];//深度优先搜索访问次序

int Low[M];//能追溯到的最早的次序
int ComponentNumber=0;//有向图强连通分量个数
int Index=0;//索引号
vector<int> Edge[M];//邻接表表示
int InComponent[M];//记录每个点在第几号强连通分量里
int ComponentDegree[M];//记录每个强连通分量的度

void Tarjan(int i)
{
int j;
DFN[i]=Low[i]=Index++;
isvisted[i]=1;
InStack[i]=true;
STACK[++top]=i;
for (int e=0;e<Edge[i].size();e++)
{
j=Edge[i][e];
if (DFN[j]==-1)//(i,e)中e还未被访问过
{
Tarjan(j);
Low[i]=min(Low[i],Low[j]);
}
else if (InStack[j])
Low[i]=min(Low[i],Low[j]);
}
if (DFN[i]==Low[i])
{
ComponentNumber++;
do{
j=STACK[top--];
InStack[j]=false;
push_back(j);
InComponent[j]=ComponentNumber;
}
while (j!=i);
}
}
clinjie wechat
Think about u every day