使用Prim算法（起点为0）求如下图所示的带权连通图的一颗最小生成树。(使用C++） 1 1/ |3 \4 2 5 0 - 4 - 2 8 \ |7 /3 3

为了在C++中使用Prim算法解决这个问题，我们首先需要定义一个邻接矩阵表示图的数据结构，然后实现Prim的核心算法步骤。这里是一个简化版的示例，假设图已经存储在一个二维数组中，其中`graph[i][j]`表示顶点i到顶点j的边的权重（如果不存在则为无穷大）。注意，这个例子仅适用于无环图，因为Prim算法并不保证能处理有负权重的环路。

#include <iostream>
#include <vector>
#include <queue>

// 定义邻接矩阵，假设值大于0代表存在边
int graph[5][5] = {
    {0, 3, INF, 8, INF},
    {INF, 0, 4, INF, 7},
    {INF, INF, 0, 3, INF},
    {INF, INF, INF, 0, 4},
    {INF, INF, INF, INF, 0}
};

// 边类，用于辅助查找最小权重边
class Edge {
public:
    int src, dest, weight;
    Edge(int src, int dest, int weight) : src(src), dest(dest), weight(weight) {}
};

// Prim算法
std::vector<int> prim(int start) {
    std::vector<bool> visited(5, false);
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
    pq.push({start, -1, 0}); // 源点添加到优先队列，dest设为-1

    while (!pq.empty()) {
        Edge current = pq.top();
        pq.pop();

        if (visited[current.src]) continue;

        visited[current.src] = true; // 标记为已访问

        for (int i = 0; i < 5; ++i) {
            if (graph[current.src][i] != INF && !visited[i]) {
                pq.push({i, current.src, graph[current.src][i]});
            }
        }
    }

    std::vector<int> result;
    for (bool v : visited)
        if (v) result.push_back(std::distance(result.begin(), result.end()));

    return result;
}

int main() {
    int start = 0;
    std::vector<int> tree = prim(start);

    for (int node : tree) {
        std::cout << "Node " << node << " is connected to the root with a cost of " << graph[start][node] << "\n";
    }

    return 0;
}