Tarjan算法
应用:
- 有向图的强连通分量
- 无向图割点和桥
- 双连通分量
接下来主要谈论前面两者的应用(主要是第三种还没学会)
算法简要介绍
我们需要先理解一下知识:搜索树
- 有向图的搜索树的4种边，如下图所示:
tree edge:在dfs搜索u的过程中，第一次搜索v，则(u,v)是树边
forward edge: u是v在树中祖先, 在dfs(u)的过程中v已经被访问过
back edge: u是v在树中后裔, 在dfs(u)的过程中v已经被访问过
cross edge: 若u和v没有祖先-后裔（后裔-祖先）关系，且在explore(u)前v已经被访问过
未完待续