用c++写一个点云最小生成树

点云最小生成树是一种图论问题，可以使用Kruskal算法和Prim算法来解决。下面是一个使用Kruskal算法的C++代码示例，假设点云数据存储在一个二维数组中，其中每一行表示一个点的坐标信息。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 1000; // 最大点数
const int INF = 0x3f3f3f3f; // 无穷大

int n; // 点数
double dist[MAX_N][MAX_N]; // 点之间的距离

struct Edge {
    int u, v; // 边的两个端点
    double w; // 边的权值
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

int parent[MAX_N]; // 并查集数组

// 并查集查找根节点
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// Kruskal算法求最小生成树
vector<Edge> kruskal() {
    vector<Edge> edges; // 存储边的集合
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            edges.push_back({i, j, dist[i][j]});
        }
    }
    sort(edges.begin(), edges.end()); // 按边权排序
    vector<Edge> mst; // 存储最小生成树的边
    for (int i = 0; i < n; i++) {
        parent[i] = i; // 初始化并查集
    }
    for (int i = 0; i < edges.size(); i++) {
        int u = edges[i].u, v = edges[i].v;
        int pu = find(u), pv = find(v);
        if (pu != pv) { // 如果不在同一个连通块中
            parent[pu] = pv; // 合并连通块
            mst.push_back(edges[i]); // 添加边到最小生成树
        }
    }
    return mst;
}

int main() {
    // 读入点云数据
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }
    // 求解最小生成树
    vector<Edge> mst = kruskal();
    // 输出最小生成树的权值和
    double sum = 0;
    for (int i = 0; i < mst.size(); i++) {
        sum += mst[i].w;
    }
    cout << sum << endl;
    return 0;
}

这段代码使用了一个结构体`Edge`来表示一条边，重载了小于号运算符以便进行边权排序。`kruskal()`函数使用Kruskal算法求解最小生成树，并返回最小生成树的边集合。`find()`函数是并查集的查找根节点操作，`parent`数组存储每个节点的父亲节点。最后，代码读入点云数据，求解最小生成树并输出权值和。