最小生成树——Kruskal-白红宇的个人博客

最小生成树——Kruskal

发布日期：2021-05-08 12:40:41 浏览次数：12 分类：精选文章

本文共 1933 字，大约阅读时间需要 6 分钟。

给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。以下是详细的步骤说明和代码实现。

算法思想

Kruskal算法是一种广泛用于求解最小生成树的高效方法，尤其适用于稀疏图。其核心思想可以总结为以下几个步骤：

排序边：将所有边按权重从小到大进行排序。这一步的时间复杂度为O(m log m)，因为需要对m条边进行排序。

并查集初始化：使用并查集数据结构来跟踪每个顶点所属的连通分量。并查集的路径压缩和按秩合并操作能够保证操作的高效性，时间复杂度分别为O(α(m))和O(m)，其中α是阿克曼函数的反函数，非常接近常数。

遍历边并选择边：按权重从小到大遍历每一条边，检查其两个端点是否在同一个连通分量中：

如果在同一个连通分量中，跳过这条边。

如果不在同一个连通分量中，合并这两个顶点的连通分量，并将这条边加入生成树，增加总权重。

判断生成树是否存在：在遍历完所有边后，检查生成树中包含的顶点数是否等于n。如果等于，说明存在最小生成树，输出总权重；如果不等于，说明图中存在环，无法形成生成树，输出impossible。

时间复杂度

Kruskal算法的时间复杂度主要由两部分决定：

边排序：O(m log m)

边遍历及并查集操作：O(m α(m))，由于α(m)非常接近于常数，时间复杂度实际上接近O(m)。

因此，Kruskal算法的总时间复杂度为O(m log m)，适用于处理较大的稀疏图。

代码实现

以下是使用C++语言实现的Kruskal算法的代码：

#include 
   
    using namespace std;const int N = 100, M = 200;int p[N];int n, m;struct edge {    int a, b, w;    bool operator<(const edge &e) const { return w < e.w; }};int find(int x) {    if (p[x] != x) {        p[x] = find(p[x]);    }    return p[x];}int kruskal() {    int res = 0, cnt = 1;    sort(e + 1, e + m + 1);    for (int i = 1; i <= m; ++i) {        int a = e[i].a, b = e[i].b, w = e[i].w;        a = find(a), b = find(b);        if (a != b) {            p[a] = b;            res += w;            cnt++;        }    }    return cnt == n ? res : -1;}int main() {    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; ++i) {        p[i] = i;    }    for (int i = 1; i <= m; ++i) {        int a, b, w;        scanf("%d%d%d", &a, &b, &w);        e[i] = {a, b, w};    }    int t = kruskal();    if (t == -1) {        puts("impossible");    } else {        printf("%d\n", t);    }    return 0;}

代码解释

数据结构定义：

struct edge定义了边的结构，包含两个顶点和权重，并支持按权重排序。

int p[N];用于并查集操作，记录每个顶点的父节点。

并查集函数：

int find(int x);实现路径压缩，找到x的根节点。

Kruskal主函数：

初始化生成树的总权重和顶点数。

排序边。

遍历每条边，检查其两个端点是否连通，若不连通则合并并加入生成树。

检查生成树是否包含所有顶点，返回结果。

输入处理：

读取顶点数和边数。

初始化并查集。

读取并存储所有边。

输出结果：

根据Kruskal函数的返回值输出impossible或最小生成树的总权重。

总结

通过以上方法，可以有效地求解给定图的最小生成树问题。Kruskal算法的高效性和代码的简洁性使其成为处理此类问题的理想选择。

上一篇：基础算法——子矩阵的和

下一篇：最小生成树——朴素版Prim算法

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！