Tarjan 算法总结
一些概念
连通:无向图中的任意两点都可以互相到达。
强连通:有向图中的任意两点都可以互相到达。
连通分量:无向图的极大连通子图。
强连通分量:有向图的极大强连通子图。
DFS 生成树:对一张图(有向无向均可)进行深度优先遍历得到的生成树。
树边:在 DFS 生成树上的边。
前向边:由子树的根连向子树内的非树边。
返祖边:由结点连向其祖先的边。
横叉边:除上面三种之外的边。
求强连通分量
对于结点 \(u\),记录两个信息 \(dfn_u\) 和 \(low_u\)。
\(dfn\) 表示时间戳,即第几个被遍历到的点。
\(low\) 表示从当前点开始,经过的边的两个端点均未处在已找出的强连通分量中,能到达最小的时间戳。
在 dfs 的过程中,将经过的点塞进一个栈里面。一旦发现 \(dfn_u=low_u\) 就一直弹栈直至弹出结点 \(u\),弹出的这些点就构成了一个强连通分量。
然后考虑如何求出 \(low_u\),枚举 \(u\) 的每条出边 \((u,v)\)。
结点 \(v\) 未遍历过,先递归处理该点,这样 \((u,v)\) 就成了树边,然后 \(low_u\gets\min(low_u,low_v)\)。
结点 \(v\) 已遍历过。
- 结点 \(v\) 处在一个已找出的强连通分量中,根据定义直接跳过。
- 结点 \(v\) 未处在已找出的强连通分量中,这样 \((u,v)\) 就成了非树边,同样地,\(low_u\gets\min(low_u,low_v)\)。
\(low\) 数组其实是在找一条向上的路径,而两个强连通分量是不可能有公共点的,所以我们才会有经过边的限制。
但是还有一个问题,\(low\) 数组有时会不能更新完全,怎么办呢?
按照边 \(1\to 2\to 3\to 4\to 5\to 6\) 的顺序走,仔细分析可以发现,\(low_3\) 没有更新完全的原因是 \(low_2\) 没有更新完全,而不是 \(low_3\gets \min(low_3,low_2)\) 导致的。
所以问题出在已遍历过的情况中。
但其实是没有关系的,\(low\) 数组的目的仅仅是判断当前强连通块是否能够继续向上合并。
所以可以在将 \(low_v\) 换成 \(dfn_v\)。
那么算法的正确性就很显然了,在合法的情况下(\(low\) 的定义)尽可能将当前强连通分量扩大。
最新文章
- JavaScript触屏滑动API介绍
- listener监听器的相关知识
- Winscp sftp远程linux服务器需要预设密码,怎么解决
- iOS中集成ijkplayer视频直播框架
- app 后端技术
- [APAC]自动发送邮件
- background-image中url找不到路径,背景图像无法显示
- 超强vim配置
- c++ 基础学习: 左值 概念cocos2d-x3.0的实际应用
- sql server获取当前日期
- Socket原理
- CCASS四种交收指令
- Oracle SQL篇(三)Oracle ROWNUM 与TOP N分析
- soot的安安装与使用
- VUE依赖webpack分别给开发环境和生产环境配置不同的常量值并在项目中动态引用
- SQL Server的JOIN是支持使用小括号修改执行顺序的
- python工具的选择
- UIWindow 介绍:概述、作用、主要属性及方法
- mysql非主键自增长
- (一)问候MyBatis3