Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 其它算法 » , ,

LCA问题的Tarjan算法

LCA问题(Least Common Ancestors,最近公共祖先问题),是指给定一棵有根树T,给出若干个查询LCA(u, v)(通常查询数量较大),每次求树T中两个顶点u和v的最近公共祖先,即找一个节点,同时是u和v的祖先,并且深度尽可能大(尽可能远离树根)。
LCA问题有很多解法:线段树、Tarjan算法跳表RMQ与LCA互相转化等。本文主要讲解Tarjan算法的原理及详细实现。

一 LCA问题

LCA问题的一般形式:给定一棵有根树,给出若干个查询,每个查询要求指定节点u和v的最近公共祖先。

LCA问题有两类解决思路:

  • 在线算法,每次读入一个查询,处理这个查询,给出答案。
  • 离线算法,一次性读入所有查询,统一进行处理,给出所有答案。

一个LCA的例子如下。比如节点1和6的LCA为0。

lca

二 算法思路

Tarjan算法是离线算法,基于后序DFS(深度优先搜索)和并查集。如果不熟悉并查集,可以查看并查集及其在最小生成树中的应用

算法从根节点root开始搜索,每次递归搜索所有的子树,然后处理跟当前根节点相关的所有查询。

算法用集合表示一类节点,这些节点跟集合外的点的LCA都一样,并把这个LCA设为这个集合的祖先。当搜索到节点x时,创建一个由x本身组成的集合,这个集合的祖先为x自己。然后递归搜索x的所有儿子节点。当一个子节点搜索完毕时,把子节点的集合与x节点的集合合并,并把合并后的集合的祖先设为x。因为这棵子树内的查询已经处理完,x的其他子树节点跟这棵子树节点的LCA都是一样的,都为当前根节点x。所有子树处理完毕之后,处理当前根节点x相关的查询。遍历x的所有查询,如果查询的另一个节点v已经访问过了,那么x和v的LCA即为v所在集合的祖先。

其中关于集合的操作都是使用并查集高效完成。

算法的复杂度为,O(n)搜索所有节点,搜索每个节点时会遍历这个节点相关的所有查询。如果总的查询个数为m,则总的复杂度为O(n+m)

比如上面的例子中,前面处理的节点的顺序为4->7->5->1->0->…。

当访问完4之后,集合{4}跟集合{1}合并,得到{1,4},并且集合祖先为1。然后访问7。如果(7,4)是一个查询,由于4已访问过,于是LCA(7,4)为4所在集合{1,4}的祖先,即1。7访问完之后,把{7}跟{5}合并,得到{5,7},祖先为5。然后访问5。如果(5,7)是一个查询,由于7已访问过,于是LCA(5,7)为7所在集合{5,7}的祖先,即5。如果(5,4)也是一个查询,由于4已访问过,则LCA(5,4)为4所在集合{1,4}的祖先,即1。5访问完毕之后,把{5,7}跟{1,4}合并,得到{1,4,5,7},并且祖先为1。然后访问1。如果有(1,4)查询,则LCA(1,4)为4所在集合{1,4}的祖先,为1。1访问完之后,把{1,4,5,7}跟{0}合并,得到{0,1,4,5,7},祖先为0。然后剩下的2后面的节点处理类似。

三 算法实现

接下来提供一个完整算法实现。

使用邻接表方法存储一棵有根树。并通过记录节点入度的方法找出有根树的根,方便后续处理。

const int mx = 10000; //最大顶点数
int n, root;		  //实际顶点个数,树根节点
int indeg[mx];		  //顶点入度,用来判断树根
vector<int> tree[mx]; //树的邻接表(不一定是二叉树)

void inputTree() //输入树
{
	scanf("%d", &n); //树的顶点数
	for (int i = 0; i < n; i++) //初始化树,顶点编号从0开始
		tree[i].clear(), indeg[i] = 0;

	for (int i = 1; i < n; i++) //输入n-1条树边
	{
		int x, y; scanf("%d%d", &x, &y); //x->y有一条边
		tree[x].push_back(y); indeg[y]++;//加入邻接表,y入度加一
	}

	for (int i = 0; i < n; i++) //寻找树根,入度为0的顶点
		if (indeg[i] == 0) { root = i; break; }
}

使用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 father[mx], rnk[mx]; //节点的父亲、秩
void makeSet() //初始化并查集
{
	for (int i = 0; i < n; i++) father[i] = i, rnk[i] = 0;
}
int findSet(int x) //查找
{
	if (x != father[x]) father[x] = findSet(father[x]);
	return father[x];
}
void unionSet(int x, int y) //合并
{
	x = findSet(x), y = findSet(y);
	if (x == y) return;
	if (rnk[x] > rnk[y]) father[y] = x;
	else father[x]  = y, rnk[y] += rnk[x] == rnk[y];
}

再就是Tarjan算法的核心代码。

在调用Tarjan之前已经初始化并查集给每个节点创建了一个集合,并且把集合的祖先赋值为自己了,因而这里不用给根节点x单独创建。

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

下面是主程序,再加一个样例输入输出作为测试。

int main()
{
	inputTree();  //输入树
	inputQuires();//输入查询

	makeSet(); 
	for (int i = 0; i < n; i++) ancestor[i] = i; 
	memset(vs, 0, sizeof(vs)); //初始化为未访问
	Tarjan(root);
	/*前面例子相关的一个输入输出如下:
	8  
	0 1   0 2   0 3   1 4   1 5   5 7   3 6
	7
	1 4   4 5   4 7   5 7   0 5   4 3   1 6
	7和4的最近公共祖先为:1
	5和4的最近公共祖先为:1
	5和7的最近公共祖先为:5
	1和4的最近公共祖先为:1
	6和1的最近公共祖先为:0
	3和4的最近公共祖先为:0
	0和5的最近公共祖先为:0
	*/
}
上一篇: 下一篇:
  1. 你好,请教个问题,博主Tarjan算法中的ancestor数组感觉有点多余了,请问这个数组是起什么作用的

    • 后续遍历过程中,同一个集合中的点跟将要访问到的点会有同样的lca,ancestor的值即保存这个lca。本来可以把这个lca作为这个集合的根,但是并查集在合并过程中不能保证这一点,于是另开一个数组进行保存。

  2. void unionSet(int x, int y) //合并
    {
    x = findSet(x), y = findSet(y);
    if (x == y) return;
    if (rnk > rnk ) father = y;
    else father = x, rnk += rnk == rnk ;
    /*
    // 这个顺序是错的,默认是把 x 的父亲设成 y ,而实际应该是默认 y 的父亲为 x
    // 尽管这样做,也能输出正确的查询结果,但并查集构成的树结构乱了。
    if (rnk > rnk ) father = x;
    else father = y, rnk += rnk == rnk ;
    */
    }

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

    unionSet(x, tree ); //将子树节点与根节点x的集合合并
    ancestor[findSet(x)] = x;//合并后的集合的祖先为x

    如果在第一步合并之后,大集合的祖先不是x,那么第二步又将这个祖先的父节点设置为x,那么将出现环。接下来你在find的时候,会死循环的。。。

  4. 而且,你每次将子集的父节点都弄成x,这叫合并?这叫强行挂在它下面!

  5. 建议作者应该解释一下,int ancestor[mx]; //已访问节点集合的祖先,这个的作用。
    正是因为这个,整个算法才正确。原来集合的父节点统一是在进行find,然后根据find的结果在ancestor中查询得到的。
    谢谢!整个过程没有问题!谢谢!

  6. 博主,你的文章写得很棒,欢迎来我的博客进行交流哦。
    我的博客网址是:http://www.qizishi.com

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论