强连通分量(SCC)


强联通

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

强连通图

如果 在一个有向图G中,任意两个点都强连通,我们就叫这个图,强连通图。

强连通分量

在一个有向图G中,有一个子图,这个子图是一个强连通图,我们就叫这个子图叫做强连通分量

如图[1,2,3]构成的子图是强连通分量

算法

Tarjan

应用

缩点


如果本文帮助到了你,帮我点个广告可以咩(o′┏▽┓`o)


文章作者: Anubis
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Anubis !
评论
  目录