C++图论强连通分量讲解

前言:

强连通分量好强，老师好喜欢（考）。

概念:

在有向图G中，如果两点互相可达，则称这两个点强连通，如果G中任意两点互相可达，则称G是强连通图。

    1、一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

    2、非强连通有向图的极大强连通子图，称为强连通分量。

在这张图中，{1,2,3,4}是一个强联通分量{5},{6}分别是另外两个强联通分量。

实现方法：

1.Kosaraju算法

我们先来看这样一张图，这是一个有两个强联通分量的一个有向图。如果我们对这个有向图进行遍历，我们如果是从A这边开始，那么只需要一个DFS就可以搜索完整个有向图，但我们如果从B这边开始，则需要两个DFS。很显然，我们这个有向图有两个强联通分量，那么，我们选择合适的起始位置（B这边的点）才能得到正确的答案。

可是我们该如何实现呢？

1、随意给起点进行DFS(一般从1开始），每次在DFS回溯的过程中进行标记，得到一个后序遍历的顺序的表。

2、对原图G进行反向，得到反图R，按照步骤1中得到的表，从后往前进行DFS遍历。

3、在步骤2中，使用了多少次的DFS，就有多少个强联通分量。

想一想，步骤2就是反着走能够回到目标节点，那么这就是一个强连通分量呀。

所以使用了多少次的DFS，就有多少个强联通分量。

2.Tarjan算法（推荐）

Tarjan算法是基于DFS的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

定义DFN[u]为节点u的搜索次序编号，Low[u]为u或u的子树能追溯到的最早的栈中节点。初始化时，DFN[u]=Low[u]=编号

将搜索到的u压入栈中，枚举所有u出去的边，如果v没有被访问，那么继续找，并在回溯时，计算Low[u]=min(Low[u],Low[v]),如果v在栈内，那么Low[u]=min(Low[u],DFN[v]).当u没有下一个节点可以搜索时，判断DFN[u]是否等于Low[u]，如果相等，则将v退栈，直到退出u为止，这次退出的所有点即为一个连通分量。

对于最开始那个图， 我们从1这个点开始，一直搜索到6，这时，DFN[6]=Low[6],且没有可以继续深入的点，那么，退出直到u=v为止，这时，栈内退出6，即{6}是一个强连通分量。

接下来，返回到节点5，发现DFN[5]=Low[5]，且5没有其他的路径搜索，那么，同样将栈内的点退出，直到u=v，得到{5}是一个强联通分量。

接下来返回3点，然后继续搜索4点，把4加入栈，发现4有一条边连向1,且1已在栈中，所以Low[4]=1,6已经出栈，返回3，此时，3没有其他的点可以继续搜索，更新Low[3]=Low[4]=1.

继续返回节点1，发现可以继续访问节点2，那么，访问2，发现2还有另外一条边连向4，发现4还在栈中，更新Low[2]=DFN[4]=5,返回1。此时，1已经没有其他可以搜索的点了，那么，把节点出栈，直到u=v为止，此时出栈的这些点{1,3,4,2}组成一个强连通分量。

而为什么我要推荐这个算法呢？

主要是时间复杂度的问题，第一个方法的时间复杂度为点数加边数*2，而第二个为点数加边数。

大数据之后优势就明显了。