c++普利姆最小生成树算法

下面是C++实现的Prim最小生成树算法，具体思路和实现过程如下：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 100; // 最大顶点数
const int INF = 0x3f3f3f3f; // 无穷大

int graph[MAX][MAX]; // 图的邻接矩阵
int lowcost[MAX]; // 记录从U到V-U具有最小代价的边
int closest[MAX]; // 记录最小边在U中的顶点
bool vis[MAX]; // 标记顶点是否已经加入U
int n; // 顶点数

void prim(int start) {
    memset(vis, false, sizeof(vis)); // 初始化标记数组
    vis[start] = true; // 将起点加入U
    for (int i = 1; i <= n; i++) {
        lowcost[i] = graph[start][i]; // 初始化lowcost数组
        closest[i] = start; // 初始化closest数组
    }
    for (int i = 1; i < n; i++) { // 循环n-1次
        int mincost = INF, v = -1;
        for (int j = 1; j <= n; j++) { // 找到距离U最近的顶点
            if (!vis[j] && lowcost[j] < mincost) {
                mincost = lowcost[j];
                v = j;
            }
        }
        if (v == -1) return; // 如果找不到，退出循环
        vis[v] = true; // 将v加入U
        cout << closest[v] << " " << v << endl; // 输出最小生成树的边
        for (int j = 1; j <= n; j++) { // 更新lowcost和closest数组
            if (!vis[j] && graph[v][j] < lowcost[j]) {
                lowcost[j] = graph[v][j];
                closest[j] = v;
            }
        }
    }
}

int main() {
    // 读入图的邻接矩阵和顶点数
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> graph[i][j];
        }
    }
    prim(1); // 从1号顶点开始构建最小生成树
    return 0;
}