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

LCA问题的跳表算法

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

二 算法思路

跳表算法是在线算法,其需要O(nlogn)的复杂度进行初始化,然后每进行一个查询需要O(logn)复杂度进行解答。

使用跳表解决LCA问题时,对每个节点i维护了一个数组anc[i][j],表示i的第2^j个祖先的节点。有了这个数组后,节点x沿着树往上跳2^k层之后,就变成了节点anc[x][k]。当待查询的两个节点u和v在同一层时,我们把uv每次向上跳2的幂次的距离,最后同时到达了u和v的LCA节点。

可以知道,由于每次跳的距离都是2的幂,如果把uv和其LCA节点间的深度差用二进制表示,则其中的每个出现1的位置就是uv每次所要跳的距离。比如,要查找5和6的LCA,则把5和6都往上跳2^1层,同时到达0,0即为所求LCA。

但如果0上面还有很多节点,则5和6同时往上跳比2更大的距离(如4)时,也会到达同样的节点,但并不是LCA(不是最近)。

为了避免这个问题,我们在跳的时候不要让他们到达相同的节点,这样就不会跳过头了。最终u和v会跳到其LCA的下一层,u和v的父亲就是他们的LCA。即,查找5和6的LCA时,5最终会跳到1,6会跳到3,它们的父亲0为要求的LCA。

当待查询的两个节点u和v不在同一层时,假如u的层数比较深。这是我们先把u跳到和v同一层的祖先中,然后再使用上述相同层的方法。把u每次往上跳2的幂次的层数,如果跳了之后在v的上方了,则不跳,否则就跳。可以知道,将u和v之间的深度差用二进制表示,则其中每个出现1的位置就是要跳的距离。比如,要查找7和6的LCA,首先把7往上跳到和6同一层的5中,然后再使用上述方法求5和6的LCA即可。

三 算法实现

下面通过代码实现更加精确地描述算法。

首先我们使用上次相同的方法使用邻接表方法存储一棵有根树,并通过记录节点入度的方法找出有根树的根。

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

数组anc[i][j]表示i的第2^j个祖先的节点,其计算方法为:

  • j=0时,anc[i][j]表示节点i的父亲节点par[i],这个par数组可以预先得到。
  • j>0时,此时求i的第2^j个祖先,可以转化先为求i的第2^(j-1)个祖先,再求这个祖先的第2^(j-1)个祖先。

这样可以按j从小到大的顺序进行求解,每个anc[i][j]只需O(1)时间得到。总的复杂度为O(nlogn),其代码如下。

int anc[mx][30]; //anc[i][j]表示节点i的第2^j个祖先节点
void calAnc() //初始化anc数组
{
	for (int i = 0; i < n; i++) 
			anc[i][0] = par[i]; //边界情况,父亲
	
	for (int j = 1; (1 << j) < n; j++)
		for (int i = 0; i < n; i++)
			if (anc[i][j-1] != -1) //注意超出根节点的情况
				anc[i][j] = anc[anc[i][j-1]][j-1];
}

上面使用到了父亲节点的信息,这个信息可以在建立有根树之后遍历得到。

int par[mx]; //par[x]表示节点x的父亲节点
void calPar(int x, int y) //初始化par数组
{
	par[x] = y; //x为当前节点,y为父亲节点(root的话为-1)
	for (int i = 0; i < tree[x].size(); i++)
		calPar(tree[x][i], x);
}

在查询过程中需要用到每个节点的深度信息,先求出来以供使用。

int dep[mx]; //dep[x]表示节点x的深度
void calDep(int x, int y) //初始化dep数组
{
	dep[x] = y; //x为当前节点,y为深度
	for (int i = 0; i < tree[x].size(); i++)
		calDep(tree[x][i], y+1);
}

以上三个初始化代码整合在一个初始化函数中方便调用。

void init() //初始化
{
	calDep(root, 0); //初始化dep数组
	calPar(root, -1);//初始化par数组
	calAnc();        //初始化anc数组
}

现在可以进行查询的处理了。

把深度较深的节点放在p中,然后把p跳到和q同样的深度,再后p和q一起往上跳。

int query(int p, int q) //查询p和q的最近公共祖先
{
	if (dep[p] < dep[q]) swap(p, q);//令p为深度较深的一个

	int log = 1; //log(dep[p])的下取整,为跳的最大距离
	while ((1 << log) <= dep[p]) log++;
	log--;

	//将p跳到与q同一层的地方
	for (int i = log; i >= 0; i--)
		if (dep[p] - (1 << i) >= dep[q])
			p = anc[p][i];

	if (p == q) return q; //检查是否和q重合

	//公共跳到最近公共祖先的下面
	for (int i = log; i >= 0; i--)
		if (anc[p][i] != -1 && anc[p][i] != anc[q][i])
			p = anc[p][i], q = anc[q][i];

	return par[p];//父亲即为最近公共祖先
}

下面是一个使用的样例,输入树之后只有进行init初始化即可进行查询。

同时进行跟上次一样内容的测试。

int main()
{
	inputTree();			//输入树
	init();					//初始化
	int m; scanf("%d", &m); //查询个数
	while (m--)
	{
		int u, v; scanf("%d%d", &u, &v);//查询u和v的LCA
		printf("%d和%d的最近公共祖先为:%d\n", u, v, query(u, v));
	}
	
	/*前面例子相关的一个输入输出如下:
	8
	0 1   0 2   0 3   1 4   1 5   5 7   3 6
	7
	1 4
	1和4的最近公共祖先为:1
	4 5
	4和5的最近公共祖先为:1
	4 7
	4和7的最近公共祖先为:1
	5 7
	5和7的最近公共祖先为:5
	0 5
	0和5的最近公共祖先为:0
	4 3
	4和3的最近公共祖先为:0
	1 6
	1和6的最近公共祖先为:0
	*/
}
上一篇: 下一篇:

我的博客

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

站内搜索

最新评论