最近看代碼時看到Tarjan算法，搜索了一下，是個經(jīng)典的求LCA（Least Common Ancestor)算法。奇怪的是，網(wǎng)上一般的介紹只會給出偽碼，而且有關(guān)集合的實現(xiàn)都沒有。為理解它還想了半天。目前有些細節(jié)還沒有完全想清楚(主要和wikipedia上給出的偽碼實現(xiàn)并不完全一致)，但根據(jù)我的理解，我的實現(xiàn)應(yīng)該是可以完成功能。
基本描述：
本身是一個從根開始的深度優(yōu)先搜索
1 為輸入節(jié)點構(gòu)建一個單節(jié)點的樹 // MAKE_SET
2 對每個子節(jié)點，遞歸調(diào)用該算法完成子樹內(nèi)所有查詢，
再將子節(jié)點的ancester指向本節(jié)點，歸并結(jié)果樹 // UNION
3 處理完所有子節(jié)點后，將本節(jié)點標(biāo)為checked
4 遍歷查詢集中和該節(jié)點有關(guān)的查詢，檢查另一個節(jié)點是否已標(biāo)為checked，如果是的話說明
1） 該節(jié)點在本節(jié)點的子樹
2） 該節(jié)點和本節(jié)點在另一節(jié)點的子樹中，而且該節(jié)點已被查詢
無論哪種情況，檢查該節(jié)點所在樹的根就是這兩個節(jié)點的LCA節(jié)點
如果沒有標(biāo)識checked，只需簡單跳過，當(dāng)遍歷到該節(jié)點時就可以完成查詢了
下面是java的實現(xiàn)代碼和簡單測試
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
白色天堂 閱讀(2239)
評論(0) 編輯 收藏