Massive Algorithms: LCA - Tarjan >> NoAlGo博客

LCA - Tarjan >> NoAlGo博客

LCA问题的Tarjan算法 » NoAlGo博客
http://blog.csdn.net/csyzcyj/article/details/10051173

首先根据LCA的定义，我们可以想到一种最简单的方法来求u，v的LCA：分别从u，v开始向根节点走，当这两个点走到第一个相同的节点时，这个节点就是LCA（u，v）

但是这样求效率不够，求一次的最坏的时间复杂度就是O(N)，若是再多来几个询问就会超时

现在介绍一种当询问次数为Q，节点数为N时时间复杂度为O(N+Q)的离线求LCA的算法：Tarjan算法

这种算法是基于DFS和并查集来实现的。设fa[x]为x的父亲，dist[x]为x节点到根节点的距离。首先从一号根节点(记为u)开始访问他的每一个子节点(记为v)，并用根节点与当前访问的子节点的距离更新dist值，即dist[v]=dist[u]+map[v][u]，其中map[v][u]表示v到u的距离，然后将当前子节点当做根点用上述同样步骤递归下去，并在递归回溯后将其fa[v]值更新，这样的目的是保证子节点v的所有子树全部被访问过。

现在我们需知道第k个询问的LCA是什么，那么这个操作应在询问中两个节点的子树全部访问完的基础上再进行。对于现在状态的根点u，访问它的子节点v，若v点“作过”根点，即被递归过，才能保证v的所有子树被全部访问完，这时才能将与之有关的询问<即询问中包含v点>更新其LCA=get(v)，get为并查集，即找到v所在集合的起点，因为并查集在这里的作用就是将同一子树中的子节点的父亲指向该子树的根节点，相当于归为了一个集合，这个集合的起点就是当前子树的根节点。

这样，从1号根节点出发，向下递归直到到达叶子节点位置，树中每个节点都被访问过了一次，在回溯后，为了对每个询问（记总询问次数为Q）更新LCA值访问了相关点，则时间复杂度为O(N)+O(Q)，因此这是个O(N+Q)的算法！

http://blog.csdn.net/v_july_v/article/details/18312089

一种是在线算法，相当于循序渐进处理；
另外一种则是离线算法，如Tarjan算法，相当于一次性批量处理，一开始就知道了全部查询，只待询问。

2.1、什么是Tarjan算法

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

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

引用此文的一个例子，如下图（不同颜色的结点相当于不同的集合）：

假设遍历完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。

于此，我们可以得知：若两个结点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算法，即每个结点只遍历一次，怎么做到的呢，请看下文讲解。

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

LCA(u){
Make-Set(u)
ancestor[Find-Set(u)]=u
对于u的每一个孩子v{
LCA(v)
Union(u)
ancestor[Find-Set(u)]=u
}
checked[u]=true
对于每个(u,v)属于P{
if checked[v]=true
then {
回答u和v的最近公共祖先为 ancestor[Find-Set(v)]
}
}
}

LCA(u) {
对于u的每一个孩子v {
LCA(v)
Union(u,v)
}
checked[u]=true
对于每个(u,v)属于P {
if checked[v]=true then 回答u和v的最近公共祖先为 ancestor[Find-Set(v)]
}
}

这里可以看到是深度优先的计算，并且每个子集都优先计算子树，之后把全部的父节点都指向集合的父节点，这样的作用是比如一个二叉树，左子树单独进行处理，使得两点都在左子树上的节点的最近公共节点是左子树的根节点，当处理完后和根节点组合，进入右节点的时候，可以看到所有的节点和左子树的最近公共节点就是根节点，但是右子树内部的都单独在一个集合中，另外更右的子树没有处理过，不进行计算。按照这个方式，不断的这样处理，就通过递归从左向右不断处理，完成整个过程。

3. 还有需要注意的一点就是（u，v）这个顺序很重要，因此每个uv的组合需要先做两次的存储，实际uv和vu只会处理一个

public class LCA_Tarjan<T> {
public static class Node<T>{
T data; //Node的数据
Node<T> father; //父节点/祖先节点
List<Node<T>> children;
public Node(){}
public Node(T data){
this.data = data;
this.father = this;
children = new ArrayList<Node<T>>();
}
}
public static class Pair<T>{
Node<T> p, q;
Node<T> lca;
public Pair(Node<T> p, Node<T> q){
this.p = p;
this.q = q;
}
}
List<Pair<T>> list; //结果
Map<Node<T>,List<Node<T>>> pairs; //对应于(u,v)，对于一个元组需要存储uv和vu
Map<Node<T>,Boolean> checked; //对应于checked[]
public List<Pair<T>> getLCA(Node<T> root, List<Pair<T>> list){
checked = new HashMap<Node<T>,Boolean>();
this.list = new LinkedList<Pair<T>>();
//构建所有需要查询的元组
pairs = new HashMap<Node<T>,List<Node<T>>>();
for(Pair<T> p : list){
if(pairs.get(p.p)==null)
pairs.put(p.p, new LinkedList<Node<T>>());
pairs.get(p.p).add(p.q);
if(pairs.get(p.q)==null)
pairs.put(p.q, new LinkedList<Node<T>>());
pairs.get(p.q).add(p.p);
}
//进入实际算法
LCA(root);
return this.list;
}
private void LCA(Node<T> u){
//完全依照伪码部分实现
for(Node<T> v:u.children){
LCA(v);
union(u, v);
}
checked.put(u, true);
if(pairs.get(u)!=null){
for(Node<T> n : pairs.get(u)){
Boolean b = checked.get(n);
if(b!=null && b){
Pair<T> pair = new Pair<T>(u,n);
pair.lca = find(n);
list.add(pair);
}
}
}
}
//--------------------------------------------------------------------
//并查集操作
/**
* 找到祖先节点
* @param x
* @return
*/
public Node<T> find(Node<T> x){
//当自己是祖先的时候直接返回
if (x == x.father){
return x;
}
//当自己的父节点不是祖先的时候，压缩树直接连接到祖先节点
x.father = find(x.father);
return x.father;
}
/**
* x和y节点之间有连接，将其所属集合连接。rank值小的树加到rank值大的树下面。相同时y加到x下。
* @param x
* @param y
*/
public void union(Node<T> x, Node<T> y){
Node<T> xFather = find(x);
Node<T> yFather = find(y);
//当两个结合不联通的时候根据rank值，将rank值小的树加到rank值大的树下面
if(xFather==yFather){
return;
}else{
yFather.father = xFather;
}
}
}

http://blog.csdn.net/cxllyg/article/details/7635992

int f[MAX];//每个节点所属集合
int r[MAX];//r是rank（秩）合并
int indegree[MAX];//保存每个节点的入度
int visit[MAX];//只有0和1，表示节点是否已处理完毕
vector<int> tree[MAX], Qes[MAX];//数，待查询的节点组合
int ancestor[MAX];//祖先集合
void init(int n)//初始化
{
for(int i=1; i<=n; i++)
{
r[i]=1;//初始秩为1
f[i]=i;//每个节点的父节点初始为自身
indegree[i]=0;
visit[i]=0;
ancestor[i]=0;
tree[i].clear();
Qes[i].clear();
}
}
int find(int n)//查找n所在集合，并压缩路径
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}
int Union(int x, int y)//合并函数，若属于同一分支则返回0，成功合并返回1
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<r[b])
{
f[a]=b;
r[b]+=r[a];
}
else
{
f[b]=a;
r[a]+=r[b];
}
return 1;
}
void LCA(int u)//tarjan求最近公共祖先
{
ancestor[u]=u;
int size=tree[u].size();
//一个一个子节点处理
for(int i=0; i<size; i++)
{
LCA(tree[u][i]);
Union(u, tree[u][i]);
ancestor[find(u)]=u;
}
//处理完子节点，置visit[u]=1
visit[u]=1;
//求当前节点与有关的节点的最近公共祖先
size=Qes[u].size();
for(i=0; i<size; i++)
{
if(visit[Qes[u][i]]==1)//如果这个节点已处理过
{
cout<<ancestor[find(Qes[u][i])]<<endl;
continue;
}
}
}
int main()
{
int n=16;//树的总节点
init(n);
int s, t;
//构造树
//输入要查询最近公共祖先的两个节点
cin>>s>>t;
//如果s在t左边，那么在遍历完s时还不能求得LCA，所以这里相当于访问两次，在访问t时即可求得结果
Qes[s].push_back(t);
Qes[t].push_back(s);
for(int i=1; i<=n; i++)
{
//寻找根节点
if(indegree[i]==0)//根节点的入度为0
{
LCA(i);
break;
}
}

http://noalgo.info/476.html

http://scturtle.is-programmer.com/posts/30055.html

使用vector数组query存储所有的查询。跟x相关的所有查询(x,y)都会放在query[x]的数组中，方便查找。

vector<int> query[mx]; //所有查询的内容
void inputQuires() //输入查询
{
 for (int i = 0; i < n; i++) //清空上次查询
  query[i].clear(); 

 int m; scanf("%d", &m); //查询个数
 while (m--)
 {
  int u, v; scanf("%d%d", &u, &v); //查询u和v的LCA
  query[u].push_back(v); query[v].push_back(u);
 }
}

int ancestor[mx]; //已访问节点集合的祖先
bool vs[mx];   //访问标志
void Tarjan(int x) //Tarjan算法求解LCA
{
 for (int i = 0; i < tree[x].size(); i++)
 {
  Tarjan(tree[x][i]);   //访问子树
  unionSet(x, tree[x][i]); //将子树节点与根节点x的集合合并 
  ancestor[findSet(x)] = x;//合并后的集合的祖先为x
 }
 vs[x] = 1; //标记为已访问
 for (int i = 0; i < query[x].size(); i++) //与根节点x有关的查询
  if (vs[query[x][i]]) //如果查询的另一个节点已访问，则输出结果
   printf("%d和%d的最近公共祖先为：%d\n", x, 
     query[x][i], ancestor[findSet(query[x][i])]);
}

node* getLCA(node* root, node* node1, node* node2)
{
if(root == null)
return null;
if(root== node1 || root==node2)
return root;
node* left = getLCA(root->left, node1, node2);
node* right = getLCA(root->right, node1, node2);
if(left != null && right != null)
return root;
else if(left != null)
return left;
else if (right != null)
return right;
else
return null;
}

上面的解法有一个很大的弊端就是：如需N 次查询，则总体复杂度会扩大N 倍，故这种暴力解法仅适合一次查询，不适合多次查询。

⒉在线算法倍增法
每次询问O(logN)，d[i] 表示 i节点的深度，p[i,j] 表示 i 的 2^j 倍祖先，那么就有一个递推式子 p[i,j]=p[p[i,j-1],j-1]，这样子一个O(NlogN）的预处理求出每个节点的 2^k 的祖先
，然后对于每一个询问的点对a,b的最近公共祖先就是：
先判断是否 d[a] > d[b]，如果是的话就交换一下（保证 a 的深度小于 b 方便下面的操作）然后把b 调到与a 同深度，同深度以后再把a,b 同时往上调（dec(j)) 调到有一个最小的j 满足p[a,j]!=p[b,j] (a b 是在不断更新的)，最后再把 a,b 往上调 (a=p[a,0],b=p[b,0]) 一个一个向上调直到a = b，这时 a or b 就是他们的最近公共祖先。
Read full article from LCA问题的Tarjan算法 » NoAlGo博客

LCA - Tarjan >> NoAlGo博客

2.1、什么是Tarjan算法

2.2、Tarjan算法如何而来

Labels

Popular Posts