tree_all_pairs_lowest_common_ancestor

tree_all_pairs_lowest_common_ancestor(G, root=None, pairs=None)

为树中的成对集生成最低的公共祖先。

参数

G网络X有向图(必须是树)

root节点，可选(默认：无)

要操作的子树的根。如果没有，则假定整个图只有一个源并使用该源。

pairs可迭代或节点对的迭代器，可选(默认：无)

一对对的兴趣。如果无，则默认为下的所有节点对 root 有着最低共同祖先的动物。

返回

lcas元组生成器

在……里面 pairs 和 lca 是它们最低的共同祖先。

参见

all_pairs_lowest_common_ancestor

常规DAG的类似例程

lowest_common_ancestor

一般DAG只需一对

笔记

仅在用从父代到子代的有向边表示的非空树上定义。使用Tarjan的离线最低共同祖先算法。及时奔跑 \(O(4 \times (V + E + P))\) 时间，其中4是反Ackermann函数在实际使用中可能出现的最大值，以及 \(P\) 是请求的配对数量(或 \(V^2\) 如果需要全部的话)。

Tarjan，R.E.（1979），“路径压缩在平衡树上的应用”，《ACM期刊》26（4）：690-715，doi:10.1145/322154.322161。