c++实现普里姆最小生成树算法。Prim( ); //图 G 是基于邻接矩阵存储表示的无向图，利用 Prim 算法求解图 G 的最小生成树

普里姆（Prim）算法是一种用于求解加权无向图最小生成树问题的算法。其基本思想是从图中的某一顶点开始，逐步增加边和顶点，直到生成树包含了图中所有的顶点。

以下是使用C++实现普里姆算法的一个简单示例代码：

#include <iostream>
#include <vector>
#include <climits> // 用于INT_MAX

using namespace std;

// 图的邻接矩阵表示
int minKey(vector<int>& key, vector<bool>& inMST, int V) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++) {
        if (inMST[v] == false && key[v] < min)
            min = key[v], min_index = v;
    }

    return min_index;
}

void printMST(vector<int> parent, vector<vector<int>>& graph) {
    cout << "Edge \tWeight\n";
    for (int i = 1; i < graph.size(); i++) {
        cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << " \n";
    }
}

void primMST(vector<vector<int>>& graph) {
    int V = graph.size();
    vector<int> parent(V); // 存储最小生成树
    vector<int> key(V, INT_MAX); // 键值用于选出最小权重边
    vector<bool> inMST(V, false); // 表示顶点是否已经包含在最小生成树中

    key[0] = 0; // 从顶点0开始

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, inMST, V); // 选择最小键值的顶点

        inMST[u] = true; // 将顶点加入最小生成树

        for (int v = 0; v < V; v++) {
            if (graph[u][v] && inMST[v] == false && graph[u][v] < key[v]) {
                parent[v] = u, key[v] = graph[u][v];
            }
        }
    }

    printMST(parent, graph);
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0},
    };

    primMST(graph); // 打印最小生成树

    return 0;
}

在这个示例中，图使用邻接矩阵进行存储，`graph[i][j]` 表示顶点 `i` 到顶点 `j` 的边的权重。如果 `i` 和 `j` 之间没有直接的边，则值为0。函数 `primMST` 实现了Prim算法的主体逻辑，而辅助函数 `minKey` 和 `printMST` 分别用于寻找最小键值的顶点和打印最小生成树的边。