all_pairs_lowest_common_ancestor#
- all_pairs_lowest_common_ancestor(G, pairs=None)[源代码]#
计算成对节点的最低公共祖先。
- 参数
- G网络X有向图
- pairs节点对的可迭代，可选(默认：所有对)
感兴趣的节点对。如果没有，将查找所有节点对的LCA。
- 返回
- ((node1，node2)，lca)上的迭代器，其中(node1，node2)是
- 指定的对，并且LCA是该对的最低公共祖先。
- 请注意，对于G中所有对的缺省值，我们认为
- 无序对，例如你不会同时得到(b，a)和(a，b)。
笔记
仅在非空有向非循环图上定义。
使用 \(O(n^3)\) 祖先列表算法来自：M.A.Bender，M.Farach-Colton，G.Pemmasani，S.Skiena，P.Sumazin。“树和有向非循环图中最低的公共祖先。”《算法学报》，57(2)：75-94,2005。