您现在的位置是:首页 >学无止境 >Kruskal算法、Kruskal重构树、LCA算法网站首页学无止境
Kruskal算法、Kruskal重构树、LCA算法
K r u s k a l Kruskal Kruskal 算法
K r u s k a l Kruskal Kruskal 算法是一种求解最小生成树的贪心算法。它的基本思想是从图中的边集中依次选取边,使得选出的边不会构成回路,并且满足边权和最小。
具体实现过程如下:
-
将原图中的所有边按照边权从小到大排序。
-
依次选取排序后的边,如果这条边的两个端点不在同一个连通块中,则加入该边,将它们之间的连通块合并成一个新的连通块,并把该边加入最小生成树的边集中。
-
重复上述步骤,直至加入 n − 1 n−1 n−1 条边(其中 n n n 表示原图的节点数),此时得到的边集即为原图的最小生成树。
K r u s k a l Kruskal Kruskal 算法的时间复杂度为 O ( m l o g m ) O(mlogm) O(mlogm),其中 m m m 表示原图的边数。它的优点是简单易实现,且能够处理带权图和带负权边的情况。但是,它不能处理带有自环和重边的图。
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v, w;
Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
bool operator<(const Edge& other) const {
return w < other.w;
}
};
vector<int> parent, rank;
int find(int i) {
if (parent[i] != i) parent[i] = find(parent[i]);
return parent[i];
}
void unite(int pu, int pv) {
if (rank[pu] < rank[pv]) parent[pu] = pv;
else if (rank[pu] > rank[pv]) parent[pv] = pu;
else {
parent[pu] = pv;
rank[pv]++;
}
}
vector<Edge> kruskal(int n, vector<Edge>& edges) {
// 初始化并查集
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
// 将边按照边权从小到大排序
sort(edges.begin(), edges.end());
// 初始化最小生成树和已经加入最小生成树的边数
vector<Edge> mst;
int cnt = 0;
for (const auto& e : edges) {
// 判断两个节点是否在同一个连通块中
int pu = find(e.u);
int pv = find(e.v);
if (pu == pv) continue;
// 如果不在同一个连通块中,将它们合并成一个新的连通块,并将边加入最小生成树
unite(pu, pv);
mst.push_back(e);
cnt++;
// 如果已经加入了 n-1 条边,停止算法
if (cnt == n - 1) break;
}
return mst;
}
int main() {
int n = 6;
vector<Edge> edges = { Edge(0, 1, 1), Edge(0, 2, 5), Edge(1, 2, 2), Edge(1, 3, 8),
Edge(2, 3, 3), Edge(1, 4, 3), Edge(2, 4, 6), Edge(3, 4, 7),
Edge(3, 5, 4), Edge(4, 5, 2) };
vector<Edge> mst = kruskal(n, edges);
for (const auto& e : mst) cout << e.u << " " << e.v << " " << e.w << "
";
}
这个算法也是对并查集的一个很好的运用帮助我更好理解并查集
这个算法的场景主要是:把图变成树、要求最小边权
K r u s k a l Kruskal Kruskal重构树
类似 K r u s k a l Kruskal Kruskal算法:有图可以参考
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v, w; // 边的两个端点和边权
Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
bool operator<(const Edge& other) const {
return w < other.w;
}
};
// 并查集的 find 操作
int find(int i, vector<int>& parent) {
if (parent[i] != i) parent[i] = find(parent[i], parent);
return parent[i];
}
// 并查集的 unite 操作
void unite(int pu, int pv, vector<int>& parent, vector<int>& rank) {
if (rank[pu] < rank[pv]) parent[pu] = pv;
else if (rank[pu] > rank[pv]) parent[pv] = pu;
else {
parent[pu] = pv;
rank[pv]++;
}
}
// 构建 Kruskal 重构树
void kruskal_reconstruction_tree(int n, vector<Edge>& edges, vector<vector<Edge>>& tree) {
// 初始化并查集和 Kruskal 重构树
vector<int> parent(n), rank(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
tree.resize(n);
// 将边按照边权从小到大排序
sort(edges.begin(), edges.end());
for (const auto& e : edges) {
// 判断两个节点是否在同一个连通块中
int pu = find(e.u, parent);
int pv = find(e.v, parent);
if (pu == pv) continue;
// 如果不在同一个连通块中,将它们合并成一个新的连通块,同时在 Kruskal 重构树上连接一条边
tree[e.u].push_back(e);
tree[e.v].push_back({e.v, e.u, e.w}); // 双向边
unite(pu, pv, parent, rank);
}
}
int main() {
int n = 6;
vector<Edge> edges = { Edge(0, 1, 1), Edge(0, 2, 5), Edge(1, 2, 2), Edge(1, 3, 8),
Edge(2, 3, 3), Edge(1, 4, 3), Edge(2, 4, 6), Edge(3, 4, 7),
Edge(3, 5, 4), Edge(4, 5, 2) };
vector<vector<Edge>> tree;
kruskal_reconstruction_tree(n, edges, tree);
for (int i = 0; i < n; i++) {
cout << "Node " << i << ":";
for (const auto& e : tree[i]) cout << " (" << e.v << "," << e.w << ")";
cout << "
";
}
}
K r u s k a l Kruskal Kruskal重构树的主要场景:两个点之间的最短路上的最长边
对于代码的解释:
tree
数组是用来存储 Kruskal 重构树的。
具体地,tree
是一个列表,有
n
n
n 个元素(其中
n
n
n 是原图中的顶点数),每个元素是一个列表,存储了该顶点所在的连通块内与其相邻的顶点和边的信息。例如,在 Kruskal 重构树中,如果顶点 u
连接了顶点 v
,边权为 w
,那么 tree[u]
中就包含一个元素 (v, w)
,而 tree[v]
中也包含一个元素 (u, w)
。
当 kruskal_reconstruction_tree
函数运行结束时,返回的 tree
列表就是 Kruskal 重构树的表示。我们可以遍历 tree
列表,对于每一个节点 u
,访问其相邻的节点 v
和对应的边权 w
,然后建立 u
和 v
之间边权为 w
的无向边,从而得到 Kruskal 重构树。
代码的结果应该是:
Node 0: (1,1) (2,5)
Node 1: (0,1) (2,2) (4,3) (3,8)
Node 2: (0,5) (1,2) (4,6) (3,3)
Node 3: (2,3) (1,8) (5,4) (4,7)
Node 4: (3,7) (1,3) (2,6) (5,2)
Node 5: (4,2) (3,4)
L C A LCA LCA算法
倍增 L C A LCA LCA
以下是基于倍增的 LCA 算法的 C++ 代码实现,假设树的节点编号从 0 0 0 到 n − 1 n-1 n−1,其中 n n n 是节点数,根节点的编号为 0 0 0:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10; // 最大节点数
const int LOGN = 20; // log2(MAXN)
int n; // 节点数
vector<int> adj[MAXN]; // 无根树的邻接表表示
int depth[MAXN]; // 节点深度
int parent[MAXN][LOGN]; // parent[i][j] 表示节点 i 的 2^j 级祖先
void dfs(int u, int p, int d) {
depth[u] = d;
parent[u][0] = p;
for (int i = 1; i < LOGN; ++i) parent[u][i] = parent[parent[u][i-1]][i-1];
for (int v : adj[u]) {
if (v != p) dfs(v, u, d+1);
}
}
// 计算节点 u 和节点 v 的 LCA
int lca(int u, int v) {
// 使节点 u 和节点 v 处于同一深度
if (depth[u] < depth[v]) {
swap(u, v);
}
// 将节点 u 抬升到与节点 v 同一深度
for (int i = LOGN-1; i >= 0; --i) {
if (depth[parent[u][i]] >= depth[v]) {
u = parent[u][i];
}
}
// 如果节点 u 已经是节点 v 的祖先,则此时 u 就是它们的 LCA
if (u == v) {
return u;
}
// 同时抬升节点 u 和节点 v,直到它们的父节点相同
for (int i = LOGN-1; i >= 0; --i) {
if (parent[u][i] != parent[v][i]) {
u = parent[u][i];
v = parent[v][i];
}
}
// 此时 parent[u][0](或 parent[v][0])就是它们的 LCA
return parent[u][0];
}
其中,dfs
函数用于求解每个节点的深度和祖先信息。当递归访问到节点 u
时,首先将其深度设为 d
,并记录其父节点 p
。然后,对于
i
=
1
i=1
i=1 到
log
2
(
n
)
log_2(n)
log2(n),计算出节点 u
的第
2
i
2^i
2i 级祖先,即 parent[u][i]=parent[parent[u][i-1]][i-1]
。最后,对于节点 u
的邻接节点 v
,如果 v
不是其父节点,则调用 dfs(v, u, d+1)
计算节点 v
的深度和祖先信息。
lca
函数用于计算节点 u
和节点 v
的 LCA。首先,将节点 u
和节点 v
抬升到同一深度,具体地,如果节点 u
的深度小于节点 v
,则交换它们的值;然后从大到小枚举
i
i
i,如果节点 u
的第
2
i
2^i
2i 级祖先的深度不小于节点 v
,则将节点 u
抬升到其第
2
i
2^i
2i 级祖先。此时,如果节点 u
就是节点 v
的祖先,则节点 u
就是它们的 LCA,直接返回 u
。否则,从大到小枚举
i
i
i,同时抬升节点 u
和节点 v
,直到它们的父节点相同为止。此时,parent[u][0]
(或 parent[v][0]
)就是它们的 LCA,返回即可。