文章/答案/技术大牛

发布

社区首页 >问答首页 >Tarjan离线最小共同祖先算法

问Tarjan离线最小共同祖先算法
EN

Stack Overflow用户

提问于 2013-07-24 06:42:07

回答 1查看 701关注 0票数 1

我目前正在阅读来自Tarjan的关于如何获得二叉树中两个节点的最小公共祖先的算法。

我已经阅读了Wikipedia中的伪代码，但我不理解它的要点。我的意思是我不能在任何给定的二叉树上应用该算法。我也试图在Google上找到一些关于每个步骤的解释，但我没有得到任何有价值的东西。所以，如果有人能帮助我理解这个算法是如何在二叉树上工作的，那就太好了。

data-structures

回答 1

Stack Overflow用户

发布于 2013-08-19 09:42:05

除了给定的二叉树之外，您还应该实现另一个名为不相交集的数据结构来应用此算法。除了这种数据结构，还有三种主要的方法:MAKE-SET、联合、查找集。我强烈建议你阅读“算法导论”的第21章“不相交集合的数据结构”，以更好地理解。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/17826935

复制

离线Tarjan算法-最近公共祖先问题

编程算法二叉树

转载自Tarjan算法 LCA问题（Least Common Ancestors，最近公共祖先问题），是指给定一棵有根树T，给出若干个查询LCA(u, v)（通常查询数量较大），每次求树T中两个顶点u和v的最近公共祖先，即找一个节点，同时是u和v的祖先，并且深度尽可能大（尽可能远离树根）。 LCA问题有很多解法：线段树、Tarjan算法、跳表、RMQ与LCA互相转化等。本文主要讲解Tarjan算法的原理及详细实现。一 LCA问题 LCA问题的一般形式：给定一棵有根树，给出若干个查询，每个查询要求指定节点u

老白

2018/03/19

1.8K0

最近公共祖先详解_共同祖先

https java 网络安全编程算法

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168771.html原文链接：https://javaforall.cn

全栈程序员站长

2022/09/22

4710

【算法-字节笔试-中等难度】Tarjan算法求解公共祖先问题LCA，并介绍倍增算法

数据分析编程算法

今天字节笔试的第二题，详情由于保密协议不能上网，但是大意就是给一大堆节点，去求LCA。递归直接爆栈，用stack写递归有一个点，改进优化了一下有两个点…… 我印象中这个算法挺简单的，就搜了一下，果然找到了。不是，现在校招算法题都这么丧病了吗。由于保密协议，不能放代码。后面放Tarjan算法学习笔记。

千灵域

2022/06/17

2720

图论--LCA--Tarjan（离线）

* * 给出一颗有向树，Q个查询 * 输出查询结果中每个点出现次数 * 复杂度O(n + Q); */ const int MAXN = 1010; const int MAXQ = 500010; // 查询数的最大值 // 并查集部分 int F[MAXN]; // 需要初始化为-1 int find(int x) { if (F[x] == -1) { return x; } return F[

风骨散人Chiam

2020/10/28

3150

Tarjan算法

component min

SCC即强连通分量，即一个图的子图，其中的点能相互到达，全称是strongly connected component。

饶文津

2020/06/02

5790

Tarjan算法

编程算法

tarjan算法一个关于有向图的联通性的神奇算法。基于DFS（迪法师）算法，深度优先搜索一张有向图。名词的储备，有备无患强连通(strongly connected)：在一个有向图G里，设两个点 a、b。发现，由a有一条路可以走到b，由b又有一条路可以走到a，我们就叫这两个顶点（a，b）强连通。强连通图(Strongly Connected Graph)：如果在一个有向图G中，每两个点都强连通，我们就叫这个图，强连通图。强连通分量(strongly connected c

机器学习算法工程师

2018/03/06

8560

tarjan算法

编程算法

说到以Tarjan命名的算法，我们经常提到的有3个，其中就包括本文所介绍的求强连通分量的Tarjan算法。而提出此算法的普林斯顿大学的Robert E Tarjan教授也是1986年的图灵奖

triplebee

2018/01/09

9650

tarjan算法详解

编程算法数据结构

tarjan算法讲解。 tarjan算法，一个关于图的联通性的神奇算法。基于DFS算法，深度优先搜索一张有向图。！注意！是有向图。根据树，堆栈，打标记等种种神奇方法来完成剖析一个图的工作。而图的联通性，就是任督二脉通不通。。的问题。了解tarjan算法之前你需要知道：强连通，强连通图，强连通分量，解答树（解答树只是一种形式。了解即可）强连通(strongly connected)：在一个有向图G里，设两个点 a b 发现，由a有一条路可以走到b，由b又有一条路可以走到a，我们就叫这两个顶点（a，

attack

2018/04/12

1.9K0

LCA 最近公共祖先

编程算法

LCA 最近公共祖先 Tarjan(离线)算法的基本思路及其算法实现　　　　首先是最近公共祖先的概念(什么是最近公共祖先？)：　　　　在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。　　　　换句话说，就是两个点在这棵树上距离最近的公共祖先节点。　　　　所以LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。　　　　有人可能会问：那他本身或者其父亲节点是否可以作为祖先节点呢？　　　　答案是肯定的，很简单，按照人的亲

Angel_Kitty

2018/04/08

1.5K0

AcWing 1171. 距离(Tarjan 离线求树上lca）

这道题本质上就是要搞懂无根树上任意两点距离就是各自到根节点距离之和再减去两倍的lca节点到根节点距离

glm233

2021/03/11

4350

tarjan系列算法代码小结

编程算法数据结构深度学习

个人使用，可能不是很详细强联通分量这里的dfn可以写成low 因为都是在栈中，只要保证该节点的low值不为本身即可 void tarjan(int now) { dfn[now]=low[now]=++tot; s.push(now); vis[now]=1; for(int i=headE[now];i!=-1;i=E[i].nxt) { if(!dfn[E[i].v]) tarjan(E[i].v),low[now]=

attack

2018/04/10

7580

LeetCode 1257. 最小公共区域（最小公共祖先）

编程算法

给你一些区域列表 regions ，每个列表的第一个区域都包含这个列表内所有其他区域。

Michael阿明

2021/02/19

6300

客户端基本不用的算法系列：Tarjan 算法的思路

编程算法

在之前的《客户端基本不用的算法系列：从 floodfill 到图的连通性》一文中，我们已经了解了在无向图中的割点和桥的定义。

用户2932962

2019/07/19

1.1K0

bgr2gray_tarjan算法

视频处理面向对象编程 java https 网络安全

//ffmpeg变量 AVPicture pFrameYUV,pFrameBGR; uint8_t * ptmp; struct SwsContext* imgCtx = NULL;

全栈程序员站长

2022/09/30

2180

TarJan 算法求解有向连通图强连通分量

编程算法 http

在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

RainMark

2019/09/10

1.9K0

Tarjan 算法求解强连通分量

编程算法

在《Tarjan 算法的思路》中我们已经给出了 Tarjan 算法中的比较重要的几个元素，我们在这里重新复习一下：

用户2932962

2019/07/27

1.1K0

二元最近的共同祖先问题（O(n) time 而且，只有一次遍历，O(1) Space （它不考虑函数调用栈空间））

编程算法二叉树 java https 网络安全

首先可以参考这个博客http://blog.csdn.net/cxllyg/article/details/7635992 ，写的比較具体，包含了节点包含父指针和不包含父指针的情况，还介绍了经典的Tarjan算法。

全栈程序员站长

2022/07/06

2590

算法模板——LCA（最近公共祖先）

编程算法数据结构

实现的功能如下——在一个N个点的无环图中，共有N-1条边，M个访问中每次询问两个点的距离原理——既然N个点，N-1条边，则说明这是一棵树，而且联通。所以以1为根节点DFS建树，然后通过求两点的LCA的方式，先求得最近公共祖先，然后再通过深度来求出两点距离 1 type 2 point=^node; 3 node=record 4 g:longint; 5 next:point; 6 end; 7

HansBug

2018/04/10

1.1K0

最低公共祖先java_洛谷是啥

https java 网络安全

输入格式第一行包含三个正整数 N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。

全栈程序员站长

2022/09/22

2040

两个节点的最近公共祖先_今日排列三21253

https java 网络安全

输入格式第一行包含三个正整数 N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。

全栈程序员站长

2022/09/22

2180

相似问题

从最低共同祖先重建树的算法名称？

Tarjan算法，递归错误

114

XAML风格共同祖先

查找树中两个节点的最小共同祖先

查找java中两个节点的最小共同祖先

114

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

社区富文本编辑器全新改版！诚邀体验～

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

问Tarjan离线最小共同祖先算法
EN