数据结构-最小生成树的Kruskal算法的实现

缺乏、安全感 2024-03-17 11:21 3阅读 0赞

**目录**

1. 什么是最小生成树

2. Kruskal算法的原理

3. Kruskal算法的实现

4. C++代码实现

--------------------

## 1. 什么是最小生成树 ##

最小生成树是一种用于解决连通图的问题的算法，它的目的是找到一个连通图的所有节点的子集，使得这个子集中的所有节点都能够互相到达，并且这个子集的边权值之和最小。最小生成树的应用非常广泛，例如在网络设计、电路设计、城市规划等领域都有着重要的应用。

## 2. Kruskal算法的原理 ##

Kruskal算法是一种贪心算法，它的基本思想是从图中的所有边中选择权值最小的边，然后将这条边加入到最小生成树的边集合中。接着，再从剩余的边中选择权值最小的边，如果这条边不会形成环，则将其加入到最小生成树的边集合中。重复这个过程，直到最小生成树的边集合中包含了所有节点。

具体实现过程如下：

1. 将所有边按照权值从小到大排序。  
2. 从权值最小的边开始，依次判断这条边的两个端点是否在同一个连通块中，如果不在同一个连通块中，则将这条边加入到最小生成树的边集合中，并将这两个端点合并到同一个连通块中。  
3. 重复步骤2，直到最小生成树的边集合中包含了所有节点。

## 3. Kruskal算法的实现 ##

Kruskal算法的实现需要用到并查集数据结构，用于判断两个节点是否在同一个连通块中。并查集是一种用于维护集合的数据结构，它支持合并集合和查询元素所属集合的操作。

具体实现过程如下：

1. 定义一个结构体Edge，用于存储边的信息，包括起点、终点和权值。  
2. 将所有边按照权值从小到大排序。  
3. 初始化并查集，将每个节点都初始化为一个单独的连通块。  
4. 依次遍历每条边，判断这条边的两个端点是否在同一个连通块中，如果不在同一个连通块中，则将这条边加入到最小生成树的边集合中，并将这两个端点合并到同一个连通块中。  
5. 重复步骤4，直到最小生成树的边集合中包含了所有节点。

## 4. C++代码实现 ##

Kruskal算法是一种常用的最小生成树算法，下面是C++实现Kruskal算法的代码：

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    const int MAXN = 1005;
    int n, m;
    int fa[MAXN];
    
    struct Edge {
        int u, v, w;
        bool operator<(const Edge& e) const {
            return w < e.w;
        }
    } edges[MAXN * MAXN];
    
    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }
    
    void merge(int x, int y) {
        fa[find(x)] = find(y);
    }
    
    int kruskal() {
        sort(edges, edges + m);
        for (int i = 1; i <= n; i++) fa[i] = i;
        int ans = 0, cnt = 0;
        for (int i = 0; i < m; i++) {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            if (find(u) != find(v)) {
                merge(u, v);
                ans += w;
                cnt++;
                if (cnt == n - 1) break;
            }
        }
        return ans;
    }
    
    int main() {
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            cin >> edges[i].u >> edges[i].v >> edges[i].w;
        }
        int ans = kruskal();
        cout << ans << endl;
        return 0;
    }

其中，\`Edge\`结构体表示一条边，\`find\`函数和\`merge\`函数分别用于查找和合并两个节点所在的集合，\`kruskal\`函数用于计算最小生成树的权值和。

在主函数中，首先读入节点数\`n\`和边数\`m\`，然后读入每条边的起点、终点和权值，最后调用\`kruskal\`函数计算最小生成树的权值和并输出。