最近做一个功能，需要对场景图中的多个节点回溯其最近公共祖先，这是一个常用的应用，搜索了一下，有tarjan算法。tarjan算法是一种离线算法，它需要一次输入所有的询问，然后有根节点开始进行深度优先遍历（DFS），在深度优先遍历的过程中，进行并查集（见文章参考链接）的操作，同时查询询问，返回结果。下面介绍实现代码及算法流程：
#include<iostream> #include<vector> using namespace std; const int MAX=17; int f[MAX]; //每个节点所属集合？ int r[MAX]; //r是rank（秩） 合并 int indegree[MAX]; //保存每个节点的入度 int visit[MAX]; //只有0和1，表示某节点id是否已处理完毕 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; //祖先为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) { int a=find(x); int b=find(y); if(a==b) return 0; //相等的话,x向y合并 else if (r[a] < r[b]) { f[a] = b; r[b] += r[a]; //小的秩合并向大的秩 } else if(r[a] == r[b]) //两秩相等，合并到左边的秩 { f[b] = a; r[a] += r[b]; } else { f[b] = a; r[a] += r[b]; } return 1; }//合并函数，如果属于同一分支则返回0，成功合并返回1 void LCA(int u) { 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; //让u的父节点祖先为u，因为是回溯操作，一定能保证集合的祖先是最近祖先 } visit[u]=1; size = Qes[u].size(); for(int i=0;i<size;i++) { //如果已经访问了问题节点,就可以返回结果了. if(visit[Qes[u][i]]==1) { cout<<ancestor[find(Qes[u][i])]<<endl; //如果这个点处理过，那么这个祖先就是共同祖先 // return; continue; } } } int main() { int n = 16; init(n); //数的总节点数 int s,t; //先构造树 tree[8].push_back(5);indegree[5]++; tree[8].push_back(4);indegree[4]++; tree[8].push_back(1);indegree[1]++; //对节点ID为8的节点添加3个子节点，相应的子节点增加入度 tree[5].push_back(9);indegree[9]++; tree[4].push_back(6);indegree[6]++; tree[4].push_back(10);indegree[10]++; tree[1].push_back(14);indegree[14]++; tree[1].push_back(13);indegree[13]++; tree[6].push_back(15);indegree[15]++; tree[6].push_back(7);indegree[7]++; tree[10].push_back(11);indegree[11]++; tree[10].push_back(16);indegree[16]++; tree[10].push_back(2);indegree[2]++; tree[16].push_back(3);indegree[3]++; tree[16].push_back(12);indegree[12]++; //输入查询 cin>>s>>t; //相当于询问两次，如果t在s的左边，那么在遍历完s时将无法得出结果 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; } } return 0; }算法步骤：1 由跟节点开始，进行深度优先遍历，遍历到叶子节点，置其对应的visit[i] = 1; 2 将父节点与子节点进行合并（将他们置于同一个集合，详细看union代码），然后，将集合的祖先置为当前节点。（要注意回溯的过程，一定是保证高层次的） 3 询问查询，即qes[u][i]，u是查询节点之一（正好是当前节点），i是另一个查询节点，如果i此时已被处理完毕，说明i在u的左边，那么i所在集合（并不是像有些文章说的i的父节点，这概念不正确）的祖先一定u，i的最近共同祖先（如果u，i在同一子树，则很好理解，如果u，i在不同子树，那么i所在集合的祖先也是u的祖先（注意回溯，上升，下降））；如果i此时未被处理，说明i在u的右边，对于u，i的询问只能跳过，但是对i，u的询问可以处理。
这个是两个节点共同祖先的查询，多个的话就用前两个的查询结果与下一个组成一个查询，依次类推。参考问题链接:http://poj.org/problem?id=1330参考代码链接:http://kmplayer.iteye.com/blog/604518 (此代码结果是正确的，但代码的一些概念不太正确)参考知识链接：http://my.chinaunix.net/space.php?uid=1721137&do=blog&id=181005 ； http://hi.baidu.com/%B1%B1%BE%A9%CE%D2%B0%AE%C4%E3/blog/item/aaa01dc630e1940a9d163d0b.html感谢相关文章作者！