Kruskal 算法求最小生成树

本文来源于离散数学上机的题目：Kruskal算法在神经网络中的应用

标题：Kruskal算法在神经网络中的应用
类别：循环、选择语句
时间限制：1
内存限制：256
问题描述：根据ALL标准将大脑分为90个区，得到90个节点的全连接图，为了有效去除冗余特征，加快分类速度加强泛化能力，可以用最小生成树算法简化图得到简化的特征向量，所设计程序能够通过编译，并能够求出给定无向连通加权图的一棵最小生成树。
输入说明：第一行输入原图的点数m和边数n，以空格隔开。第二行到第n+1行输入原图中每条边的起点、终点和权值，以空格隔开。
输出说明：输出每条边的起点、终点和权值，以空格隔开，并换行输出下一条边的起点、终点和权值，直到输出所有结果。输出顺序按权值从小到大。
输入样例：
4 5
1 2 7
1 3 10
1 4 3
2 4 20
3 4 15
输出样例：
1 4 3
1 2 7
1 3 10
输入方式：控制台
判定规则：忽略首尾空白、忽略空行、忽略大小写、数据之间只保留一个空白。

Kruskal 算法

1. 新建图${\displaystyle G}$，${\displaystyle G}$中拥有原图中相同的节点，但没有边

2. 将原图中所有的边按权值从小到大排序

3. 从权值最小的边开始，如果这条边连接的两个节点于图${\displaystyle G}$中不在同一个连通分量中，则添加这条边到图${\displaystyle G}$中

4. 重复3，直至图${\displaystyle G}$中所有的节点都在同一个连通分量中

程序实现的核心是如何判断图中的两节点是否联通（判断图中是否存在环），可以用并查集来实现。

并查集

Kruskal算法会在输出的MST中先加入点，因此我们将每个节点的parent赋为自身。随后对输入的每一条边进行判断：如果该边连接的两个节点的父节点不同，则向MST中加入这条边，并更新并查集，此处可以进行路径压缩（Path Compression）。

for (int i = 0; i < n; i++) {
    int parentU = unionFind(unionSet, edges[i].u);
    int parentV = unionFind(unionSet, edges[i].v);
    if (parentU != parentV) {
        MST.push_back(edges[i]);
        unionSet[parentV] = parentU;
    }
}

完整代码

完善剩余的部分很简单，完整代码如下：

// Kruskal's algorithm

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Edge {
    int u, v, weight;
};

bool cmp(Edge a, Edge b) {
    return a.weight < b.weight;
}

int unionFind(int* unionSet, int x) {
    if (unionSet[x] != x)
        return unionFind(unionSet, unionSet[x]);

    return unionSet[x];
}

int main() {
    int m, n;

    cin >> m >> n;
    Edge edges[n];
    vector<Edge> MST;
    int unionSet[m+1];

    for (int i = 0; i < n; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    }
    
    for (int i = 0; i < m+1; i++) {
        unionSet[i] = i;
    }

    sort(edges, edges + n, cmp);

    for (int i = 0; i < n; i++) {
        int parentU = unionFind(unionSet, edges[i].u);
        int parentV = unionFind(unionSet, edges[i].v);
        if (parentU != parentV) {
            MST.push_back(edges[i]);
            unionSet[parentV] = parentU;
        }
    }

    for (int i = 0; i < MST.size(); i++)
        cout << MST[i].u << ' ' << MST[i].v << ' ' << MST[i].weight << endl;

    return 0;
}

后续完善

你可以手写一个并查集类