tarjan算法大意

时间:2023-03-08 16:47:04

Tarjan算法 (以发现者Robert Tarjan命名)是一个在图中寻找强连通分量的算法。算法的基本思想为:任选一结点开始进行深度优先搜索dfs(若深度优先搜索结束后仍有未访问的结点,则再从中任选一点再次进行)。搜索过程中已访问的结点不再访问。搜索树的若干子树构成了图的强连通分量。

应用到咱们要解决的LCA问题上,则是:对于新搜索到的一个结点u,先创建由u构成的集合,再对u的每颗子树进行搜索,每搜索完一棵子树,这时候子树中所有的结点的最近公共祖先就是u了

引用此文的一个例子,如下图(不同颜色的结点相当于不同的集合):

tarjan算法大意

假设遍历完10的孩子,要处理关于10的请求了,取根节点到当前正在遍历的节点的路径为关键路径,即1-3-8-10,集合的祖先便是关键路径上距离集合最近的点。

比如:

  • 1,2,5,6为一个集合,祖先为1,集合中点和10的LCA为1
  • 3,7为一个集合,祖先为3,集合中点和10的LCA为3
  • 8,9,11为一个集合,祖先为8,集合中点和10的LCA为8
  • 10,12为一个集合,祖先为10,集合中点和10的LCA为10

得出的结论便是:LCA(u,v)便是根至u的路径上到节点v最近的点。

2.2、Tarjan算法如何而来

但关键是 Tarjan算法是怎么想出来的呢?再给定下图,你是否能看出来:分别从结点1的左右子树当中,任取一个结点,设为u、v,这两个任意结点u、v的最近公共祖先都为1。

tarjan算法大意

于此,我们可以得知:若两个结点u、v分别分布于某节点t 的左右子树,那么此节点 t即为u和v的最近公共祖先。更进一步,考虑到一个节点自己就是LCA的情况,得知:

  • 若某结点t 是两结点u、v的祖先之一,且这两结点并不分布于该结点t 的一棵子树中,而是分别在结点t 的左子树、右子树中,那么该结点t 即为两结点u、v的最近公共祖先。

这个定理就是Tarjan算法的基础。

一如上文1.1节我们得到的结论:如果当前结点t 满足 u <t < v,说明u和v分居在t 的两侧,故当前结点t 即为最近公共祖先

而对于本节开头我们所说的如果要求多个任意两个结点的最近公共祖先,则相当于是批量查询,即在很多组的询问的情况下,或许可以先确定一个LCA。例如是根节点1,然后再去检查所有询问,看是否满足刚才的定理,不满足就忽视,满足就赋值,全部弄完,再去假设2号节点是LCA,再去访问一遍。

可此方法需要判断一个结点是在左子树、还是右子树,或是都不在,都只能遍历一棵树,而多次遍历的代价实在是太大了,所以我们需要找到更好的方法。这就引出了下面要阐述的Tarjan算法,即每个结点只遍历一次,怎么做到的呢,请看下文讲解。

2.3、Tarjan算法流程

Tarjan算法流程为:

Procedure dfs(u);
begin
设置u号节点的祖先为u
若u的左子树不为空,dfs(u - 左子树);
若u的右子树不为空,dfs(u - 右子树);
访问每一条与u相关的询问u、v
-若v已经被访问过,则输出v当前的祖先t(t即u,v的LCA)
标记u为已经访问,将所有u的孩子包括u本身的祖先改为u的父亲
end

普通的dfs 不能直接解决LCA问题,故Tarjan算法的原理是dfs + 并查集,它每次把两个结点对的最近公共祖先的查询保存起来,然后dfs 更新一次。如此,利用并查集优越的时空复杂度,此算法的时间复杂度可以缩小至O(n+Q),其中,n为数据规模,Q为询问个数。

2.4、Tarjan算法的应用举例

引用此文中的一个例子。

i) 访问1的左子树

STEP 1:从根结点1开始,开始访问结点1、2、3

节点

1

2

3

4

5

6

7

8

祖先

1

2

3

         
tarjan算法大意

STEP 2:2的左子树结点3访问完毕

节点

1

2

3

4

5

6

7

8

祖先

1

2

2

         
tarjan算法大意

STEP 3:开始访问2的右子树中的结点4、5、6

节点

1

2

3

4

5

6

7

8

祖先

1

2

2

4

5

   
tarjan算法大意

STEP 4:4的左子树中的结点5访问完毕

节点

1

2

3

4

5

6

7

8

祖先

1

2

2

4

4

     
tarjan算法大意

STEP 5:开始访问4的右子树的结点6

节点

1

2

3

4

5

6

7

8

祖先

1

2

2

4

4

6

   
tarjan算法大意

STEP 6:结点4的左、右子树均访问完毕,故4、5、6中任意两个结点的LCA均为4

节点

1

2

3

4

5

6

7

8

祖先

1

2

2

4

4

4

   
tarjan算法大意

STEP 7:2的左子树、右子树均访问完毕,故2、3、4、5、6任意两个结点的LCA均为2

节点

1

2

3

4

5

6

7

8

祖先

1

2

2

2

2

2

   

tarjan算法大意

如上所述:进行到此step7,当访问完结点2的左子树(3),和右子树(4、5、6)后,结点2、3、4、5、6这5个结点中,任意两个结点的最近公共祖先均为2。

ii) 访问1的右子树

STEP 8:1的左子树访问完毕,开始访问1的右子树

节点

1

2

3

4

5

6

7

8

祖先

1

1

1

1

1

1

   

tarjan算法大意

STEP 9:开始访问1的右子树中的结点7、8

节点

1

2

3

4

5

6

7

8

祖先

1

1

1

1

1

1

7

 
tarjan算法大意

STEP 10

节点

1

2

3

4

5

6

7

8

祖先

1

1

1

1

1

1

7

8

tarjan算法大意

STEP 11

节点

1

2

3

4

5

6

7

8

祖先

1

1

1

1

1

1

7

7

tarjan算法大意

STEP 12:1的右子树中的结点7、8访问完毕

节点

1

2

3

4

5

6

7

8

祖先

1

1

1

1

1

1

1

1

tarjan算法大意

当进行到此step12,访问完1的左子树(2、3、4、5、6),和右子树(7、8)后,结点2、3、4、5、6、7、8这7个结点中任意两个结点的最近公共祖先均为1。

STEP 13:1的左子树、右子树均访问完毕

节点

1

2

3

4

5

6

7

8

祖先

1

1

1

1

1

1

1

1

tarjan算法大意
    通过上述例子,我们能看到,使用此Tarjan算法能解决咱们的LCA问题。