Prim算法实现最小生成树 一般情况下，假设n个顶点分成两个集合：U（包含已落在生成树上的结点）和 V-U（尚未落在生成树上的顶点），则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。 输入图的相关信息，使用Prim算法，生成最小生成树（从图中序号最小的顶点开始）。 注意：选择邻接顶点时，若多个邻接顶点，按顶点编号从小到大的顺序，优先选择编号小的邻接顶点。 输入说明： 先输入图中顶点个数和边的数目，空格间隔； 然后输入每个顶点的数据； 最后依次输入每条边的起始和终止顶点的位序及边上的权值，格式为：顶点1位序 顶点2位序 权值。 输出说明： 按生成次序依次输出最小生成树中的各边的起始顶点位序和终止顶点位序，用英文逗号间隔，且用一对圆括号括起来。 注意：所有顶点的数据，不论是数字还是字符，顶点的位序按ASCII码值从小到大设置。使用c++实现，并给出完整代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n, m;
int g[MAXN][MAXN]; // 存图
int d[MAXN]; // 存储当前点到生成树的最小距离
bool vis[MAXN]; // 标记点是否已经加入生成树

void prim() {
    memset(d, INF, sizeof(d)); // 初始化当前点到生成树的最小距离为正无穷
    memset(vis, false, sizeof(vis)); // 初始化所有点都未加入生成树
    d[1] = 0; // 从第一个点开始生成
    int res = 0; // 存储最小生成树的权值和
    for (int i = 1; i <= n; i++) { // 枚举n个点
        int u = -1; // 存储当前未加入生成树的距离最小的点
        for (int j = 1; j <= n; j++) { // 寻找当前未加入生成树的距离最小的点
            if (!vis[j] && (u == -1 || d[j] < d[u])) {
                u = j;
            }
        }
        vis[u] = true; // 将距离最小的点加入生成树
        if (i != 1) { // 不是第一个加入生成树的点，则将当前点与生成树的最小边加入生成树
            cout << "(" << g[u][d[u]] << "," << u << ")";
            res += g[u][d[u]];
        }
        for (int v = 1; v <= n; v++) { // 更新其他点到生成树的最小距离
            if (!vis[v] && d[v] > g[u][v]) {
                d[v] = g[u][v];
                d[u] = v;
            }
        }
    }
    cout << endl << res << endl; // 输出最小生成树的权值和
}

int main() {
    cin >> n >> m;
    memset(g, INF, sizeof(g));
    for (int i = 1; i <= n; i++) {
        g[i][i] = 0; // 自己到自己的距离为0
    }
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c; // 输入每个顶点的数据
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w; // 输入每条边的起始和终止顶点的位序及边上的权值
        g[u][v] = g[v][u] = w; // 无向图，需要更新两次
    }
    prim();
    return 0;
}