tarjan算法 (求最近公共祖先)

本文讲解用于求解最近公共祖先 (Least Common Ancestor, LCA) 的tarjan算法.

首先看最近公共祖先问题. 对一棵给定的有根树, 为了得知两点之间最短的路径, 显然应当先从一点运动到它们的最近公共祖先, 再直接运动到另一点. 如果每条边只能经过一次, 那么这就是唯一的路径. 这时就需要确定这两点的最近公共祖先. 对小规模的数据可以使用暴力算法, 比如对一个点的所有祖先进行dfs, 找到最近的、能到达另一点的那个祖先. 但是这个算法本身效率就很低下, 更不用提大规模数据的情形.

解决这一类问题有多种算法, 可分为在线算法和离线算法两种. “在线” 和 “离线” 是针对大规模数据的说法, 在线算法是指对每个询问 (即节点对) 即时处理的算法, 离线算法是指将所有询问存储起来以后统一处理的算法. 在线和离线会造成复杂度的很大差异, 通常来讲离线算法应当更快一些, 因为离线情形掌握了更多的信息. 这里要讲的tarjan算法是一种离线算法, 复杂度为$O(n+p)$, 其中$n$为树的节点数, $p$为询问数.

考虑优化上述的dfs. 上述的dfs显然有许多浪费, 因为上述过程中的所有节点只需要一次dfs就可以遍历完, 而上述过程中dfs的次数却与深度成正比, 这显然是没有很好地利用dfs的信息. 仔细考虑dfs的过程, 发现遍历在最近祖先处是一棵一棵子树进行的, 也就是先遍历了含有节点1的子树, 再遍历含有节点2的子树 (假设1比2先遍历到) , 我们需要找到这两棵子树 “分叉” 的地方, 而不考虑分叉处上面的情形. 那么可以考虑这样做: 针对当前的状态v, 为遍历过的每个节点u打上一个标记, 记录u和v从哪里开始 “分叉” . 如果这一操作可以在遍历到u时就做到, 那么问题就解决了. 显然初始值 (刚遍历到u时的标记) 是这个节点直接的父亲. 当遍历完他父亲的所有子树后仍没有找到节点2时, 应当返回它父亲的父亲继续搜索, 那么该节点的标记也都应当变成他的父亲的父亲. 这看起来需要再进行一次dfs从而效率和刚才一样低, 但是可以用并查集解决这一问题. 现在的过程变成, 遍历到某一结点时, 将他和他父亲合并 (在并查集中成为父亲的子树) ; 当他父亲遍历完所有子树之后, 将他父亲和他父亲的父亲合并…为了知道某个节点的标记 (分叉处) , 只需要查找该节点在并查集中的根节点.