简介

Tarjan 算法是图论中非常实用 / 常用的算法之一，能解决强连通分量，双连通分量，割点和桥，求最近公共祖先（LCA）等问题。

Tarjan 算法是基于 深度优先搜索 的算法，用于求解图的连通性问题。Tarjan 算法可以在线性时间内求出无向图的割点与桥，进一步地可以求解无向图的双连通分量；同时，也可以求解有向图的强连通分量、必经点与必经边。

名词解析

割点

若从图中删除节点 x 以及所有与 x 关联的边之后，图将被分成两个或两个以上的不相连的子图，那么称 x 为图的 割点。
image.png

桥/割边

若从图中删除边 e 之后，图将分裂成两个不相连的子图，那么称 e 为图的 桥 或 割边。
image.png

Tarjan 算法

tarjan 算法中最重要的数据结构如下：

时间戳

  • 时间戳是用来标记图中每个节点在进行深度优先搜索时被访问的时间顺序，当然，可以理解成一个序号（这个序号由小到大），用 dfn[x] 来表示。


搜索树

  • 在无向图中，我们以某一个节点 x 出发进行深度优先搜索，每一个节点只访问一次，所有被访问过的节点与边构成一棵树，我们可以称之为“无向连通图的搜索树”。


追溯值

  • 追溯值用来表示从当前节点 x 作为搜索树的根节点出发，能够访问到的所有节点中，时间戳最小的值 —— low[x]。


什么是“能够访问到的所有节点”？，其需要满足下面的条件之一即可：

  • 以 x 为根的搜索树的所有节点
  • 通过一条非搜索树上的边，能够到达搜索树的所有节点

    使用 Tarjan 算法求解无向图的割点与桥

    语雀内容

    总结

    Tarjan算法还有许多其他的用途，请参考下述链接。

没有看懂！！！

参考链接

https://mp.weixin.qq.com/s/2GCJQdsb7oy9BkqM32lU2A
https://mp.weixin.qq.com/s/8vIVRzu-oPi5TyUIMW1JGw
https://blog.csdn.net/hurmishine/article/details/75248876