Kosaraju算法、Tarjan算法分析及证明--强连通分量的线性算法

一、背景介绍

强连通分量是有向图中的一个子图,在该子图中,所有的节点都可以沿着某条路径访问其他节点。强连通性是一种非常重要的等价抽象,因为它满足

  • 自反性:顶点V和它本身是强连通的
  • 对称性:如果顶点V和顶点W是强连通的,那么顶点W和顶点V也是强连通的
  • 传递性:如果V和W是强连通的,W和X是强连通的,那么V和X也是强连通的

强连通性可以用来描述一系列属性,如自然界中物种之间的捕食关系,互相捕食的物种可以看作等价的,在自然界能量传递中处于同一位置。

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

二、Kosaraju算法描述

Kosaraju算法通过以下步骤获得一个有向图的强连通分量。

  • 在图G中,计算图G的反向图G'的深度优先搜索的逆后序排列。反向图是比如原图中有V到W的链接,那么反向图中就有W到V的链接。逆后序排列是指,在对一个图进行深度优先遍历时,先进行子节点的递归,再将本节点加入到一个栈中,最后依次出栈以获得的序列。逆后序排列有一个重要特性,就是如果有W到V的有向链接,那么实际出栈时,W仍然排在V的前面
  • 在G中进行普通的深度优先搜索,但是搜索顺序不是按照正统的( i = 0, i < N )去依次搜索,而是以刚刚获得的逆后序排列的顺序进行搜索。
  • 每个以这个逆后序排列中的元素开始的DFS搜索,找到的所有元素,都是同一个强联通分量的元素。

为什么这个算法可以获得强连通分量呢?网上的证明很少,所以下面给出我的逻辑证明。

三、Kosaraju算法证明

我们按照算法描述的步骤往下走:

  1. 按照算法的结论,假设我们已经获得了一个逆后序排列,我们从中找两个元素,分别是V,W,W先出栈并且通过DFS找到了V。那么,V和W就是同一个联通分量的元素。到底是不是呢?
  2. 不管是不是,我们至少可以确定对于该有向图G,W有一条链接通往V,我们记作W->V。那么,对于该有向图的反向图G',确定有链接V->W
  3. 我们开始思考,在什么条件下,我们能够在反向图 G' 中获得V...W(即W先出栈)这样一个排列呢?要知道,我们刚刚确定了有链接V->W,所以逆后序排列中,应该是V排在W的前面,W...V这样啊?
  4. 所以在G'中,要么是我们之前提到的,在V->W的同时有W->V的链接;要么就是W和V之间没有任何联系,这样V的DFS结束之后,包含W的联通分量的DFS才开始遍历,才能造成W比V先出栈
  5. 但是我们已经知道,V和W不是毫无关系的,确定有链接V->W,所以第二个可能不成立,所以必然存在一个W->V的链接,也就是W和V是互相联通的!
  6. 证明完毕。

四、算法源码

 因为代码很长,放在github上了。代码是在Idea中编译运行通过的,实现了一个基本的Graph数据结构,在此基础上实现了Kosaraju类,供参考。

源文件


五、更加迅速的tarjan算法

部分内容转自https://www.byvoid.com/blog/scc-tarjan

1.Tarjan算法

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

定义DFN(u)为节点u搜索的次序编号(时间戳),Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出,

Low(u)=Min
{
    DFN(u),
    Low(v),(u,v)为树枝边,u为v的父节点
    DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)
}

当DFN(u)=Low(u)时,以u为根的搜索子树上所有节点是一个强连通分量。

算法伪代码如下

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)
}

2.算法的精要之处如下:

  • 为每个加入的节点设定序号,使得后搜索到的节点的序号一定高于前面的节点
  • 那么,如果后搜索到的节点的子节点里居然有比它本身还要小的节点,则一定出现了环。有环则必定强连通
  • 那么,把该节点的标识节点Low(u)设为发现的后向节点的值DFN(V)
  • 然后递归程序返回该节点的上级节点u-1,上级节点判断Low(u-1)的值,也把它指向了刚刚找到的后向节点
  • 最后,除了后向节点本身,所有环中的节点都指向该后向节点,那么,我们找到了一个强连通分量。

3.算法流程的演示

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

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

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

求有向图的强连通分量还有一个强有力的算法,为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法,其时间复杂度也是O(N+M)。与Trajan算法相比,Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS,不用建立逆图,更简洁。在实际的测试中,Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外,该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法,也有助于深入理解求双连通分量的Tarjan算法,两者可以类比、组合理解。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发与安全

算法:图的深度优先遍历(Depth First Search)

图的遍历和树的遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traverse Graph)。 图的遍...

37360
来自专栏python读书笔记

《python算法教程》Day5 - DFS遍历图(邻接字典)DFS简介代码示例

这是《python算法教程》的第5篇读书笔记。这篇笔记的主要内容为运用DFS(深度优先搜索,depth first search)对图(邻接字典)进行遍历。 D...

656110
来自专栏Android机动车

数据结构——图相关概念

可是现实生活中,好多关系不再是一对一或一对多,比如人和人之间的关系,会互相认识,就要考虑多对多的情况。这就是今天要介绍的——图。

11820
来自专栏算法与数据结构

数据结构 图

1-1 无向连通图至少有一个顶点的度为1 错误: 无向连通图考点: 1. 每条边连接两个顶点,所有顶点的度之和等于边数的2倍 2.记住两个特殊的无相连通图模型:...

45370
来自专栏向治洪

数据结构之图

基本概念 图(Graph):图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间...

22550
来自专栏kalifaの日々

C++迪杰斯特拉最短路径算法实现

input 第一行表示这个图有4条边,下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 ? 输入样例 out 分别...

35540
来自专栏编程理解

数据结构(八):邻接表与邻接矩阵

邻接表和邻接矩阵是图的两种常用存储表示方式,用于记录图中任意两个顶点之间的连通关系,包括权值。

25430
来自专栏机器学习实践二三事

ResNet && DenseNet(实践篇)

上篇博客说了ResNet和DenseNet的原理,这次说说具体实现 ResNet def basic_block(input, in_features, out...

26380
来自专栏机器学习与自然语言处理

判断有向图是否有圈

1. 拓扑排序 拓扑排序是对有向无圈图的顶点的一种排序:如果存在一条vi到vj的路径,则vj排在vi后面(因为只要满足这个特性就是拓扑序列,所以它不一定是唯一的...

49780
来自专栏从流域到海域

图(Graph)的常用代码集合

图的相关概念请查阅离散数学图这一章或者数据结构中对图的介绍。代码来自课本。 /*Graph存储结构*/ //邻接矩阵表示法 #define MAX_VERTEX...

39460

扫码关注云+社区

领取腾讯云代金券