`
384444165
  • 浏览: 258754 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

LCA离线算法Tarjan(1)算法介绍和最近公共祖先计算

阅读更多

之前小试的看过一些关于最近公共祖先LCA的离线算法,个人感觉很多博文说的还是不够清晰,一直没搞太懂,不知道是不是最近智商退化导致的,今天花时间细致了解了Tarjan,这篇文章主要说下算法和树结构最近公共祖先的计算,另外一些扩展应用在后续的帖子再说。

下面这篇博客中的伪码对我帮助很大,希望也能对不太明白的童鞋有帮助,后面还会提到。

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

 

这里默认了解了并查集,并查集还是比较简单,很多的博客也都说的非常清楚,具体的一个非常生动的例子:http://blog.csdn.net/ljfbest/article/details/6642769

这里给出一个基本实现的代码版本:

 

public class DisjointSet<T> {
	
	public static class Node<T>{  
	    T data;         //Node的数据
	    int rank = 0;   //祖先节点的rank,rank小的节点表示孩子少,合并的时候加入到rank大的树下
	    Node<T> father; //父节点/祖先节点
	      
	    public Node(T data){  
	        this.data = data;  
	        this.father = this;
	        this.rank = 0;
	    }
	}  
	    
	/**
	 * 找到祖先节点
	 * @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 if(xFather.rank >yFather.rank)
			yFather.father = xFather;
		else if(xFather.rank < yFather.rank)
			xFather.father = yFather;
		else{
			yFather.father = xFather;
			xFather.rank++;
		}
	}  
}

 


进入正题看Tarjan,LCA最本质的应用就是查找两个节点最近的公共节点。比如

 2和3的最近公共节点是1,4和3也是1,4和5是2。

 

伪码直接摘用的博客上的,主要在后面做一些补充。

 

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)]   
         }   
     }   
} 

 

其中,makest就是建立一个集合,makeset(u )就是建立一个只含U的集合。

findset(u)是求跟U一个集合的一个代表,一般此集合用并查集表示,也就是当前树的root节点。

union()就是把 V节点生成的子树并入U中。

ancestor就是找跟节点,一直往上找,直至某节点的父节点是自己为止。

 

对于上面显示的并查集的基本demo而言,MakeSet和ancestor操作都不需要做,因此稍微简化一下,给出段代码,重要是关注这个流程,以上面的例子来说明。

 

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)]     
     }   
} 

 

 

1.    首先考虑下用并查集,很容易做最远公共祖先(当然,树的时候就是根),然后按这个思路需要做的就是怎么找到4、5的公共节点是2

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

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

 

 因为伪码比较清楚了,搜了很多帖子,看到这段伪码想想就大概清楚了,这里就贴上代码,很多算法大牛们的代码都太不易懂了,我还是来点工程版的

 

/**
 * 对于树结构的LCA_Tarjan
 * 
 * @author Jason_wbw
 *
 */

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;
		}
	}  
}

 

 

  • 大小: 1.4 KB
分享到:
评论

相关推荐

    LCA (最近公共祖先) Tarjan & 倍增

    LCA Tarjan: 实现原理 理解:离线算法,建好树后再查询,一次DFS 吧所有查询解决完。 时间复杂度:O(n+q); n个点 q次询问 补一下:链式向前星,并查集 ,Tarjan 代码 #include #include #include #include #...

    Tarjan 的 LCA 算法

    Tarjan的LCA算法是由Robert Tarjan提出的,它是一种高效地在线性时间内求解树中两个节点的最近公共祖先的方法。这个算法的关键在于对树进行深度优先搜索(DFS)的同时,利用一个叫做“下沉路径”的概念来构建一个...

    LCA.zip_lca Tarjan pascal_lca pascal_tarjan lca pascal

    在本例中,提供的压缩包文件"LCA.zip"包含了使用Pascal语言实现的Tarjan算法来解决最近公共祖先问题的代码。 Tarjan算法是由Robert Endre Tarjan设计的一种高效算法,主要用于解决图的深度优先搜索(DFS)和强连通...

    lca求最近公共祖先

    Tarjan算法是由Robert Tarjan提出的一种在线性时间内找到图中所有简单环的算法,但在LCA问题中,它被巧妙地用于寻找最近公共祖先。该算法的核心思想是深度优先搜索结合并查集。 1. **深度优先搜索**:Tarjan算法...

    RMQ以及LCA:最近公共祖先

    给定一棵树`T`和树中的两个节点`u`和`v`,LCA问题的目标是找到`u`和`v`的最近公共祖先。即在树中寻找一个节点`x`,使得`x`是`u`和`v`的祖先,并且没有任何其他祖先比`x`更接近于`u`和`v`。 **解决方法:** LCA问题...

    Tarjan应用LCA

    标题中的“Tarjan应用LCA”指的是在图论和数据结构领域中,使用Tarjan算法来解决最近公共祖先(Least Common Ancestor, LCA)问题。最近公共祖先是指在一棵树中,两个节点的共同祖先中离根节点最远的一个。LCA问题在...

    最近公共祖先LCA(C++版).docx

    最近公共祖先(Lowest Common Ancestor,LCA) 最近公共祖先(Lowest Common Ancestor,LCA)是指在一棵树上,两个节点的最近公共祖先节点。也就是说,两个点在这棵树上的距离最近的公共祖先节点。LCA 是一个基本...

    算法之LCA与RMQ问题1

    在计算机科学领域,算法是解决问题的关键,而LCA(最近公共祖先)和RMQ(区间最值查询)是树形结构和数组处理中常见的两类问题。本文将详细介绍这两种算法及其高效解决方案。 首先,LCA(最近公共祖先)问题是在...

    contest_tarjan_LCA_源码

    让我们深入探讨一下Tarjan算法以及如何应用于寻找最近公共祖先。 首先,我们来理解最近公共祖先的概念。在一棵有根树中,两个节点u和v的最近公共祖先(LCA)是指距离根节点最近的那个节点,这个节点同时是u和v的...

    Tarjan算法

    在图论和计算机科学中,Tarjan算法是由Robert Endre Tarjan设计的一系列高效算法,主要用于解决图的相关问题,包括强连通分量、拓扑排序和最近公共祖先(Lowest Common Ancestor, LCA)等问题。这里的焦点是最近公共...

    最低公共祖先算法实现

    最低公共祖先(Lowest Common Ancestor,简称LCA)算法是数据结构与算法中的一个重要概念,主要用于处理树形结构的问题,比如在二叉树、树状数组或图中找到两个节点的最近公共祖先。在本项目中,它通过C++语言实现,...

    LCA与RMQ相关题解1

    最近公共祖先(Lowest Common Ancestor,简称LCA)问题在图论和算法中具有重要的地位,特别是在处理树形结构的数据时。LCA问题指的是在一个树形结构中,查找两个指定节点的最近公共祖先,即离这两个节点最近的共同父...

    RMQ与LCA ACM必备

    LCA,最近公共祖先,是图论中的一个重要概念,通常应用于树状结构。给定树中的两个节点u和v,LCA是指距离u和v最近的共同祖先节点。例如,在一个树形结构中,A是B和C的LCA,D是E和F的LCA。 1. **Tarjan离线算法**: ...

    数据结构求公共祖先

    此外,为了优化查询性能,可以采用预处理的方法,如LCA(Lowest Common Ancestor)数据结构,如Morris遍历或Tarjan's offline LCA算法,它们能在O(1)的时间复杂度内求解任意两个节点的最近公共祖先。 总结起来,求...

    算法刷题提高阶段-图论9

    其中,预处理方法通常使用Mo's算法或者LCA算法(如Tarjan's LCA、Floyd's LCA、LCA on Trees with LCA Queries等)来实现高效的查询。这些算法在预处理阶段会计算出树的一些特性,使得在之后的查询过程中能快速找到...

    ACM中的RMQ和LCA问题

    例如,树中的节点A、B、C...L,A和G的最近公共祖先为A,D和K的最近公共祖先为D,而B和T的最近公共祖先为B。解决LCA问题的常见算法是Tarjan离线算法,它使用并查集维护树的结构,并通过查找路径上的父节点来找到LCA。...

    Tarjan算法讲义

    Tarjan 算法是图论中非常实用 / 常用的算法之一,能解决强连通分量,双连通分量,割点和桥,求最近公共祖先(LCA)等问题。 关于 Tarjan 算法,笔者将用一系列文章系统介绍 Tarjan 算法的原理以及其主要解决的问题...

    lca.rar_LCA

    在IT领域,特别是数据结构和算法的设计中,"最近公共祖先"(Lowest Common Ancestor,简称LCA)是一个常见的问题。这个问题出现在许多场景中,比如计算机科学中的树形结构处理,生物信息学中的基因进化分析等。最近...

    LCA.zip_C++_JDI_LCA_lca并查集_分治思想

    测试文件"test"可能包含了用于测试LCA算法的样例输入和输出,以便验证算法的正确性。 总之,通过结合分治思想和并查集,我们可以高效地解决最近公共祖先问题。这种解决方案不仅适用于理论上的分析,也在实际应用中...

    算法合集之RMQ与LCA问题PPT学习教案.pptx

    在信息学竞赛和其他实际应用中,RMQ和LCA问题的解决方法多种多样,包括ST算法、Tarjan算法等。ST算法是处理一般RMQ问题的一种高效方法,其预处理时间复杂度为O(Nlog^2N),而单次查询的时间复杂度为O(1)。Tarjan算...

Global site tag (gtag.js) - Google Analytics