使用Prim算法生成最小生成树并输出点云PLY文件最小路径的C++代码

下面是使用Prim算法生成最小生成树并输出点云PLY文件最小路径的C++代码：

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

struct Point {
    double x, y, z;
};

struct Edge {
    int src, dest;
    double weight;
};

class Graph {
    int V;
    vector<Edge> edges;

public:
    Graph(int V) {
        this->V = V;
    }

    void addEdge(int src, int dest, double weight) {
        Edge edge;
        edge.src = src;
        edge.dest = dest;
        edge.weight = weight;
        edges.push_back(edge);
    }

    void primMST(vector<Point>& points) {
        vector<int> parent(V, -1);
        vector<double> key(V, INFINITY);
        vector<bool> mstSet(V, false);

        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;

        int src = 0;
        key[src] = 0;
        pq.push(make_pair(0, src));

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            mstSet[u] = true;

            for (const auto& edge : edges) {
                int v = edge.dest;
                double weight = edge.weight;

                if (mstSet[v] == false && weight < key[v]) {
                    parent[v] = u;
                    key[v] = weight;
                    pq.push(make_pair(key[v], v));
                }
            }
        }

        // Output the minimum path to PLY file
        ofstream outputFile("min_path.ply");
        outputFile << "ply" << endl;
        outputFile << "format ascii 1.0" << endl;
        outputFile << "element vertex " << V << endl;
        outputFile << "property float x" << endl;
        outputFile << "property float y" << endl;
        outputFile << "property float z" << endl;
        outputFile << "element edge " << V - 1 << endl;
        outputFile << "property int vertex1" << endl;
        outputFile << "property int vertex2" << endl;
        outputFile << "property float weight" << endl;
        outputFile << "end_header" << endl;

        for (int i = 0; i < V; i++) {
            outputFile << points[i].x << " " << points[i].y << " " << points[i].z << endl;
        }

        for (int i = 1; i < V; i++) {
            outputFile << parent[i] << " " << i << " " << key[i] << endl;
        }

        outputFile.close();
    }
};

double calculateDistance(const Point& p1, const Point& p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    double dz = p1.z - p2.z;

    return sqrt(dx * dx + dy * dy + dz * dz);
}

int main() {
    int V = 5; // Number of vertices
    Graph graph(V);

    // Sample points
    vector<Point> points = {
        {0, 0, 0},
        {1, 1, 1},
        {2, 2, 2},
        {3, 3, 3},
        {4, 4, 4}
    };

    // Calculate distances between points and add edges to the graph
    for (int i = 0; i < V; i++) {
        for (int j = i + 1; j < V; j++) {
            double distance = calculateDistance(points[i], points[j]);
            graph.addEdge(i, j, distance);
        }
    }

    graph.primMST(points);

    return 0;
}

这段代码使用Prim算法生成最小生成树，并将最小路径以PLY文件格式输出。你可以根据需要修改点的数量、坐标和边的权重。生成的PLY文件名为'min_path.ply'，包含点和边的坐标以及权重信息。