type
status
date
slug
summary
tags
category
icon
password
强连通分量简介
有向图强连通分量:在有向图G中,如果两个顶点 间有一条从到的有向路径,同时还有一条从到的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。
比如下图:
Tarjan 算法
Tarjan算法是用来求强连通分量的,它是一种基于DFS(深度优先搜索)的算法,每个强连通分量为搜索树中的一棵子树。并且运用了数据结构栈。由于栈的先进先出的性质可以保证当前在栈中的结点中先入栈的结点必然有一条通路通往后入栈的结点,这样一来判断后入栈的结点是否有一条路径通向先入栈结点就成了算法要解决的主要问题。
算法思路:
首先引入两个数组 dfn[maxn] 和 low[maxn], 其中 dfn[i] 表示编号为 i 的节点被访问时的时间戳;low[i] 表示从编号为 i 的节点可追溯到(到达)的最早被访问到的节点的时间戳。下面通过上述例子跑一遍算法,描绘出每个时刻的DFS树状态和栈中的内容。
由上述过程可得该图由三个连通分量:{5},{4},{2,3,1,0}
算法实现:
代码中有详细注释,可结合上述图例分析
运行结果
- Author:Lamyh
- URL:https://blog.ccyh.xyz/article/tarjan
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!