[C++图论] 强连通

你的名字 2022-04-25 10:24 199阅读 0赞

### 文章目录 ###

*  概念
 *  实现
 *   *  Kosaraju
     *  Tarjan
     *   *  算法流程
         *  参考代码

# 概念 #

在一个有向图中，如果说**有两个点互相可达**，那么这两个点就可说是 **强连通**。简单来说，就是在这两个点中有一个环，可以从其中一点任意抵达对面的另一点。当然，官方语言（度娘解释）是这样的：

> 强连通（Strongly Connected）是指一个有向图（Directed Graph）中任意两点v1、v2间存在v1到v2的路径（path）及v2到v1的路径。

那么有了 ***强连通*** 这个概念，既然就会有 **强连通图** 了。当然，这个其实也可以举一反三：  
**就是在一个有向图中，任意两点都可以互相可达**。  
接下来再贴度娘解释：

> 强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

而强连通图有两个性质：

> 1.  充分性：如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图.
> 2.  必要性：如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾.

当然，其实这个不懂也没有关系，接着看下面的 **强连通分量** 吧。

> 有向图的极大强连通子图，称为强连通分量(strongly connected components)。

意思也就是说，在有向图中的一些强连通子图，需要注意的是： ***一个点也算作一个强连通分量*** 哦。

只读概念有些烧脑，让我们一起来看个图理解一哈：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]

在这个图中，显然 （ 1 — 2 — 3 — 4 ） （1 — 2 — 3 — 4） （1—2—3—4）是最大的强连通分量，因为从他们中的任意一点都可抵达其他的三个点 （大家可以试下哦）。然后  5 5 5 和  6 6 6 分别是强连通分量。

# 实现 #

这里会介绍两种实现的方法，不过呢，会强烈安利第二种，而第一种则是介绍一下算法的流程。

## Kosaraju ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1]  
在这个图中大家可以很显然的看出有两个强连通分量，分别是 A 系 列 A系列 A系列和 B 系 列 B系列 B系列，可是如果说从A中的任意一点进入的话，就只需要一次就能够将所有的点遍历完，可是如果从B中的任意一点进入的话，则需要两次DFS才能够遍历完所有的点，因此，  
***找到合适的起始点至关重要***  
所以，我们可以进行两次DFS：

1.  第一次选择任一点进行DFS，然后按照遍历顺序将每个点依次存起来，按照深度越深的越后顺序。
2.  将图G变成反图G’。
3.  按照遍历顺序从后往前遍历G’，即从第一次DFS退出的那个点开始往回遍历反图。
4.  在这次DFS中遍历了几次就说明有几个强连通分量。

解释一下，假设有两个点a和b，如果说他们两个互相强连通，那么正图从a能走到b的话，反图也一定可以。  
可是为什么算法一定要这样呢？我找到一篇博客中认为说的颇有道理，附下：

> 由图（即为上图）可知：  
> 不管从A开始DFS，还是从B开始DFS，因为A到B有一条边，所以 ***最后退出DFS的点一定在A上*** ，若选最后退出DFS的点为始点（位于A中）并对上图的 **反图** 进行一次DFS，则可以得到图中的两个强连通。

but，这种方法要用两次DFS，数据一大则十分浪费时间，因此不太推荐。  
而接下来的方法却只需要一次DFS，相比起来会快上许多，而且也较好理解。

不过如果有人想学一下的话，推荐一篇[博客][Link 1]，我认为写得也是比较好的哈。。

## Tarjan ##

**接下来就是重头戏了！！！！**  
论tarjan这个人的话，那么在后面好多地方都会有他 插上一脚 的算法，不可不谓是一个神人啊。  
闲话少说，切入正题。  
![aHR0cHM6Ly9pLmxvbGkubmV0LzIwMTkvMDYvMDUvNWNmNzRmNWNjN2VkMTI1NTg2LnBuZw][]  
这里有一张图，显然，这个有向图的强连通分量应该是这几个：  
\[外链图片转存失败(img-hR4aEEH2-1563960651474)([https://i.loli.net/2019/06/05/5cf74fdfd0d1962775.png][https_i.loli.net_2019_06_05_5cf74fdfd0d1962775.png])\]  
因为1-4中所有节点可以互相到达，而5只能到6,6却不能到5，因此他们分别是不同的强连通分量。  
可是，该如何实现这个呢？我们将定义两个数组——  d f n \[ \] dfn\[ \] dfn\[\]和 l o w \[ \] low\[ \] low\[\]。  
dfn的意思是入栈的时间，也就是被访问的时间（是第几个被访问的），大家也可以看做一个*时间戳*，而low的意思则是**该节点或者是该节点的子节点所能到达的最小的时间标记**，举个例子：  
 l o w \[ u \] low\[u\] low\[u\] 代表着以u为根节点时，u或u的儿子在这棵树中所能到达的最上面的地方（因为时间标记是越到后面越大，因此取min的时候就是最先访问到的节点）。

### 算法流程 ###

1.  首先，先将 d f n \[ u \] dfn\[u\] dfn\[u\]和 l o w \[ u \] low\[u\] low\[u\]都打成新的时间戳。
2.  枚举u的儿子们v，如果说v没有被访问过，那么就访问他，并且修改 l o w \[ u \] low\[u\] low\[u\]变成v所能到达的最上面的点，即 l o w \[ u \] = m i n ( l o w \[ u \] , l o w \[ v \] ) low\[u\] = min (low\[u\], low\[v\]) low\[u\]=min(low\[u\],low\[v\])。否则，如果说v访问过了，而且此时还在栈中没有被弹出去（因为如果说被弹出去了，就说明**是其他的强连通分量，而不是这一个**），那么修改 l o w \[ u \] low\[u\] low\[u\]变成子节点的时间戳（ ***注意！！！不是子节点所能到达的最上面的点*** ）
3.  遍历结束后，如果说 d f n \[ u \] = = l o w \[ u \] dfn\[u\] == low\[u\] dfn\[u\]==low\[u\]，就说明不管怎么遍历，**u和他的儿子最大都只能遍历到他自己，也就代表着他是这个强连通分量的根**，那么此时就可以清栈了，栈顶一直到该节点都是这个强连通分量。

首先从1号节点遍历，一直遍历到6号，并且将它们分别压入栈。一直到6号节点时，他已经没有可遍历的点了，且 d f n = l o w = 4 dfn=low=4 dfn=low=4，那么就把6退出，他是第一个强连通分量，回溯。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2]  
返回到5号节点，他也没有节点可以访问了，而且 d f n = l o w = 3 dfn=low=3 dfn=low=3，5作为第二个强连通分量，退出栈并且回溯。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 3]  
返回到3号节点，还有4号节点可以访问，那么继续访问。访问4号节点时，它还可以走到1号节点，那么将4号节点的low改为dfn\[1\]。没有节点可以访问，回溯。3号节点的low也修改为1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 4]  
返回到3号节点后，也没有可以访问得了，继续回溯到1号节点，访问2节点，2访问到4时，4还在栈中，将low\[2\]改为dfn\[4\]就是5。回溯  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 5]  
回溯到1后，low=dfn，说明这又是一个强连通分量，清栈。

### 参考代码 ###

void tarjan (int u){ 
        dfn[u] = low[u] = ++indx;
        S.push (u);
        instack[u] = 1;
        for (int i = 0; i < G[u].size (); i++){ 
            int v = G[u][i];
            if (!dfn[v]){ 
                tarjan (v);
                low[u] = min (low[u], low[v]);
            }
            else if (instack[v])
                low[u] = min (low[u], dfn[v]);
        }
        if (dfn[u] == low[u]){ 
            sum ++;
            int v;
            belong[u] = sum;
            do{ 
                v = S.top ();
                belong[v] = sum;
                instack[v] = 0;
                S.pop ();
            }while (u != v);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]: /images/20220125/e2395fc0023249d2ae82ce0880943414.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1]: /images/20220125/9b8bd806562747ac90fc048c36fd898e.png
[Link 1]: https://blog.csdn.net/zyz_bz/article/details/90714967
[aHR0cHM6Ly9pLmxvbGkubmV0LzIwMTkvMDYvMDUvNWNmNzRmNWNjN2VkMTI1NTg2LnBuZw]: /images/20220125/18aee1831103436ca26f4f53a1b6abcd.png
[https_i.loli.net_2019_06_05_5cf74fdfd0d1962775.png]: https://i.loli.net/2019/06/05/5cf74fdfd0d1962775.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2]: /images/20220125/6eb180e669c343bc8e04dc3f3dde5edf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 3]: /images/20220125/d1eb6f4ee99642d0ad628502c950863a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 4]: /images/20220125/339c4258cf5d4709973b8de520045357.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 5]: /images/20220125/90cff1944eae40f3997a4af31f2261e3.png