您现在的位置是:首页 >学无止境 >Kruskal算法、Kruskal重构树、LCA算法网站首页学无止境

Kruskal算法、Kruskal重构树、LCA算法

call me by ur name 2024-06-14 17:17:37
简介Kruskal算法、Kruskal重构树、LCA算法

K r u s k a l Kruskal Kruskal 算法

K r u s k a l Kruskal Kruskal 算法是一种求解最小生成树的贪心算法。它的基本思想是从图中的边集中依次选取边,使得选出的边不会构成回路,并且满足边权和最小。

具体实现过程如下:

  1. 将原图中的所有边按照边权从小到大排序。

  2. 依次选取排序后的边,如果这条边的两个端点不在同一个连通块中,则加入该边,将它们之间的连通块合并成一个新的连通块,并把该边加入最小生成树的边集中。

  3. 重复上述步骤,直至加入 n − 1 n−1 n1 条边(其中 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,然后建立 uv 之间边权为 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 n1,其中 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,返回即可。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。