最近看代码时看到Tarjan算法，搜索了一下，是个经典的求LCA（Least Common Ancestor)算法。奇怪的是，网上一般的介绍只会给出伪码，而且有关集合的实现都没有。为理解它还想了半天。目前有些细节还没有完全想清楚(主要和wikipedia上给出的伪码实现并不完全一致)，但根据我的理解，我的实现应该是可以完成功能。
基本描述：
本身是一个从根开始的深度优先搜索
1 为输入节点构建一个单节点的树 // MAKE_SET
2 对每个子节点，递归调用该算法完成子树内所有查询，
再将子节点的ancester指向本节点，归并结果树 // UNION
3 处理完所有子节点后，将本节点标为checked
4 遍历查询集中和该节点有关的查询，检查另一个节点是否已标为checked，如果是的话说明
1） 该节点在本节点的子树
2） 该节点和本节点在另一节点的子树中，而且该节点已被查询
无论哪种情况，检查该节点所在树的根就是这两个节点的LCA节点
如果没有标识checked，只需简单跳过，当遍历到该节点时就可以完成查询了
下面是java的实现代码和简单测试
import java.util.*;
public class Tarjan{
static void lca( Node p, ArrayList<Query> q ){
MAKE_SET(p);
//FIND(p).ancester=p;
for( Node i : p.childs){
lca( i, q );
UNION( p, i );
FIND(p).ancester=p;
}
p.checked=true;
for( Query query : q ){
if( query.p1==p ){
if( query.p2.checked ){
query.result=FIND(query.p2);
}
}else if( query.p2==p ){
if( query.p1.checked ){
query.result=FIND(query.p1);
}
}else{
continue;
}
}
}
static void MAKE_SET( Node p ){
p.ancester = p;
}
static Node FIND( Node p ){
Node r=p;
for( ; r.ancester!=r; r=r.ancester );
return r;
}
static void UNION( Node p, Node q ){
q.ancester=p;
}
public static void main( String args[] ){
// create tree
Node p[]=new Node[24];
p[0]=new Node(0,null); // root
p[1]=new Node(1,p[0]);
p[2]=new Node(2,p[0]);
p[3]=new Node(3,p[0]);
p[4]=new Node(4,p[1]);
p[5]=new Node(5,p[1]);
p[6]=new Node(6,p[1]);
p[7]=new Node(7,p[2]);
p[8]=new Node(8,p[2]);
p[9]=new Node(9,p[3]);
p[10]=new Node(10,p[3]);
p[11]=new Node(11,p[3]);
p[12]=new Node(12,p[4]);
p[13]=new Node(13,p[4]);
p[14]=new Node(14,p[6]);
p[15]=new Node(15,p[8]);
p[16]=new Node(16,p[10]);
p[17]=new Node(17,p[10]);
p[18]=new Node(18,p[14]);
p[19]=new Node(19,p[14]);
p[20]=new Node(20,p[17]);
p[21]=new Node(21,p[17]);
p[22]=new Node(22,p[17]);
p[23]=new Node(23,p[11]);
// make lca query
ArrayList< Query > q= new ArrayList<Query>();
q.add( new Query(p[15], p[19]));
q.add( new Query(p[21], p[16]));
q.add( new Query(p[14], p[14]));
q.add( new Query(p[4], p[23]));
q.add( new Query(p[23], p[16]));
// lca
lca( p[0], q );
// dump results
for( Query item : q ){
System.out.println( item.p1+":"+item.p2+": result is:"+item.result );
}
}
}
class Node{
public Node( int id, Node parent ){
this.id=id;
if( parent != null ){
parent.childs.add(this);
}else{
assert this.id==0;
}
this.checked=false;
this.ancester=null;
this.childs=new ArrayList<Node>();
}
int id;
ArrayList<Node> childs;
public String toString(){
return "Node:<"+id+">";
}
Node ancester; // used for lca search
boolean checked; // used for lca search
}
class Query{
public Query( Node p1, Node p2 ){
assert p1!=null && p2!=null;
this.p1=p1;
this.p2=p2;
this.result=null;
}
Node p1;
Node p2;
Node result;
}
测试使用的树：
0
+--------------+--------------------+
| | |
1 2 3
+-----+------+ +---+ +-------+---------+
| | | | | | | |
4 5 6 7 8 9 10 11
+---+ + + +--+------+ |
| | | | | | 23
12 13 14 15 16 17
+--------+ +----+----+
| | | | |
18 19 20 21 22
PS，差点忘了，祝lp生日快乐
posted on 2008-01-07 23:15
白色天堂 阅读(2229)
评论(0) 编辑 收藏