- 一、什么是强连通分量
- 1. 概念
- 2. 强连通分量
- 二、两种dfs遍历
- 1. 方式1
- 2. 方式2
- 三、一个简单例子理解算法
- 四、更完整的一个例子
- 五、Code实现
tarjan强连通分量算法
1. 概念连通：无向图中，从任意点i可到达任一点j
强连通：有向图中，从任意点i可到达任一点j
弱连通：把有向图看作无向图时，从任意点i可到达任一点j
- 如图，强连通无论那个点，都能按照方向到达任意一点，弱连通如果强行按方向，那么B到不了C，A到不了B和C，C到不了B。但如果把他看作是无向图，那么他们也能满足连通条件。
整个图并不是强连通的，但是在某些局部区域，他确实也符合强连通的要求，如下图，整张图不算是强连通，但是局部还是能满足强连通条件的。
先访问当前节点，再递归相邻节点
- 如上图所示，先访问A，将A标记为已访问之后，我再去访问B，依次下去，B这个分支访问完了，再退回来dfs(F)。如果发现当前节点已经被访问过了，直接结束。因为既然已经被访问过了，那么他相邻的点必然也被访问过来，自然无需访问。
先递归相邻节点，再访问当前节点
- 如上图所示，实际上就是顺序变了，有点像二叉树的后序遍历？对，就是后序遍历，这也是tarjan算法的核心。
-
对于节点x，我有两个变量来表示他的信息，i表示访问顺序（时间戳），j表示按照方向进行访问，能够访问到的最早的节点的时间戳
-
如上，A的时间戳为1，B时间戳为2，C时间戳为3，D时间戳为4
-
A能访问到的最早的时间戳为1，B能访问到的最早的时间戳为2，C能先访问D，再访问到B所以最早时间戳也为2，D也是，能访问到的最早时间戳为2
-
有相同j值的节点构成一个强连通区域，如上图，B、C、D构成一个强连通区域，A自己构成一个强连通区域
- 这里肯定会有人问，那我通过什么方法来更新j的值呢，这里我们可以根据打印顺序来进行寻找，先打印E，E只能访问到自己，于是E(5,5)，然后打印D，D可以访问到B，于是D(4,2)，然后打印C，C能访问到D，D有最早时间戳2，于是C(2,2)，然后再打印B，B(2,2)，然后开始DFS(F)，说明之前的确实已经完成了打包了，B、C、D是一个强连通域，接着如上面步骤，找出AFG这个强连通域
public class Main {
static int time = 1;
static Stack stack = new Stack<>();
static int[] dfn;//表示i属性
static int[] low;//表示j属性
static int n;//节点个数
public static void main(String[] args) {
n = 10;
dfn = new int[n];//初始化
low = new int[n];//初始化
for (int i = 0; i < n; i++) {
if (dfn[i] == 0) {
DFS(i);
}
}
}
public static void DFS(int x) {
stack.push(x);
dfn[x] = time;
low[x] = time;
time++;
for (int y = 0; y < n; y++) {
if (x和y是连通的) {
if (dfn[y] == 0) {//y这个节点没有被访问过
DFS(y);
low[x] = Math.min(low[x], low[y]);//更新最早时间戳
} else if (如果y已经被访问过了，但是y在stack里面){
low[x] = Math.min(low[x], low[y]);
}
}
}
if (dfn[x] == low[x]) {//如果我将他整个儿子都完成了遍历，结果他的访问时间戳和最早时间戳相等，说明我整个强连通分量的节点全部访问完了
stack.pop();
}
}
}
