一、定位概念
最近公共祖先（LCA），指的是在一个树或有向无环图中，找到两个节点的共同祖先中深度最小的一个。
LCA问题是计算机科学中一种常见的算法问题，它有着广泛的应用。例如，可以用来处理家谱信息，或者解决大多数其他相关问题，例如计算两个版本之间的最近公共祖先或两个字符串之间的LCS（最长公共子序列）等等。
二、基本算法
LCA问题的本质是求树中两个节点的最近公共祖先，最简单的算法是遍历整棵树，记录下每个节点的祖先，比较两个节点的祖先列表，找到最后一个相同的节点即为最近公共祖先。该算法的时间复杂度为O(N^2)，其中N为节点的数量。
#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, root; //输入数据：n表示树的节点数量，m表示询问数量，u、v表示两个节点
vector<int> adj[10001]; //存储树的连接关系
vector<int> parents[10001]; //存储每个节点的祖先
void dfs(int u, int p) { //深度优先遍历
parents[u].push_back(p);
for (auto v : adj[u]) {
if (v != p) dfs(v, u);
}
}
int lca(int u, int v) { //计算最近公共祖先
if (parents[u].size() > parents[v].size()) swap(u, v);
int len1 = parents[u].size();
int len2 = parents[v].size();
for (int i = 0; i = 0; i--) {
if (parents[u][i] == parents[v][i]) return parents[u][i];
}
return root;
}
int main() {
scanf("%d%d%d", &n, &m, &root);
for (int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(root, 0); //预处理每个节点的祖先
for (int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
printf("%d\n", lca(u, v));
}
return 0;
}
三、改善算法
遍历整棵树是一种时间复杂度比较高的算法，可以对其进行改善，以达到更好的效果。改善算法的核心思想是预处理出每个节点到根节点的距离，然后通过二分查找的方法，找到两个节点深度最浅的公共祖先。
#include <bits/stdc++.h>
using namespace std;
const int N = 10001;
int n, m, u, v, root, depth[N], f[N][16]; //f数组用于辅助计算节点的距离
vector<int> adj[N];
void dfs(int u, int p) { //深度优先遍历，预处理每个节点的深度和父节点
depth[u] = depth[p] + 1;
f[u][0] = p;
for (int i = 1; (1 << i) <= depth[u]; i++) {
f[u][i] = f[f[u][i - 1]][i - 1]; //使用DP的思想，把节点的距离预处理出来
}
for (auto v : adj[u]) {
if (v != p) dfs(v, u);
}
}
int lca(int u, int v) { //利用二分查找的思想，计算最近公共祖先
if (depth[u] 0; i++) {
if (diff & 1) u = f[u][i];
diff >>= 1;
}
if (u == v) return u;
for (int i = log2(depth[u]); i >= 0; i--) {
if (f[u][i] != f[v][i]) {
u = f[u][i];
v = f[v][i];
}
}
return f[u][0];
}
int main() {
scanf("%d%d%d", &n, &m, &root);
for (int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(root, 0);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
printf("%d\n", lca(u, v));
}
return 0;
}
四、总结
本文从概念、基本算法和改善算法三个方面进行了LCA问题的详细阐述。LCA问题是计算机科学中一种常见的算法问题，在实际生活中有广泛的应用。
基础算法的核心思想是遍历整棵树，记录节点的祖先列表，计算节点的深度，比较两个节点的祖先列表，找到最后一个相同的节点即为最近公共祖先。
改善算法的核心思想是预处理出每个节点到根节点的距离，使用二分查找的方法，找到两个节点深度最浅的公共祖先，达到了比基础算法更高效的效果。
原创文章，作者：OUWUA，如若转载，请注明出处：https://www.506064.com/n/332176.html
微信扫一扫 
支付宝扫一扫 