用c++写一个点云最小生成树
时间: 2023-07-22 15:12:55 浏览: 46
好的,下面是用C++实现点云最小生成树的代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
struct Edge {
int u, v;
double w;
bool operator < (const Edge& e) const {
return w > e.w;
}
};
struct Point {
double x, y, z;
Point(double x = 0, double y = 0, double z = 0) : x(x), y(y), z(z) {}
};
double distance(const Point& a, const Point& b) {
double dx = a.x - b.x, dy = a.y - b.y, dz = a.z - b.z;
return sqrt(dx*dx + dy*dy + dz*dz);
}
int main() {
int n;
cin >> n;
vector<Point> points(n);
for (int i = 0; i < n; i++) {
double x, y, z;
cin >> x >> y >> z;
points[i] = Point(x, y, z);
}
vector<Edge> edges;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double d = distance(points[i], points[j]);
edges.push_back(Edge{i, j, d});
}
}
sort(edges.begin(), edges.end());
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int count = 0;
double sum = 0;
for (int i = 0; i < edges.size(); i++) {
int u = edges[i].u, v = edges[i].v;
double w = edges[i].w;
while (parent[u] != u) u = parent[u];
while (parent[v] != v) v = parent[v];
if (u != v) {
parent[u] = v;
count++;
sum += w;
if (count == n - 1) {
break;
}
}
}
cout << sum << endl;
return 0;
}
```
该程序使用Kruskal算法实现点云最小生成树,首先读入点的坐标,然后计算两两点之间的距离并将边加入到一个边集中,通过对边集进行排序,然后逐一判断每一条边是否属于最小生成树,最后输出最小生成树的权值之和。
希望能对您有所帮助!
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)