C++prim算法代码

Prim算法是一种用于求解最小生成树的贪心算法。C++实现Prim算法的代码如下：

const int INF = 0x3f3f3f3f; // 无穷大值
const int MAXN = 1005; // 最大顶点数

int n, m; // n表示顶点数，m表示边数
int dis[MAXN]; // 存储当前点到树的距离
int vis[MAXN]; // 标记该点是否已经被加入树中
int g[MAXN][MAXN]; // 存储图的邻接矩阵

int prim() {
    memset(dis, INF, sizeof(dis)); // 将所有点的距离初始化为无穷大
    memset(vis, 0, sizeof(vis)); // 将所有点的标记初始化为未加入树中
    int res = 0; // 最小生成树的权值之和
    dis = 0; // 从任意一个点开始都可以，这里以1号点为例

    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == -1 || dis[j] < dis[u])) {
                u = j;
            }
        }
        vis[u] = 1; // 标记该点已经被加入树中
        res += dis[u]; // 将该点到树的距离累加到最小生成树的权值之和中
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && g[u][v] != INF && g[u][v] < dis[v]) {
                dis[v] = g[u][v]; // 更新当前点到树的距离
            }
        }
    }
    return res;
}

该算法的时间复杂度为O(n^2)，其中n为顶点数。