prim算法的时间复杂度及其代码实现C++

Prim算法是一种求解最小生成树的贪心算法，其时间复杂度为O(n^2)，其中n为节点数。以下是Prim算法的C++代码实现：

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

const int N = 510;
int n, m;
int g[N][N];  // 存储图的邻接矩阵
int dist[N];  // 存储每个节点到当前生成树的最短距离
bool st[N];   // 存储每个节点是否已经加入生成树

int prim()
{
    memset(dist, 0x3f, sizeof dist);  // 初始化dist数组为无穷大
    int res = 0;  // 存储最小生成树的边权和
    for (int i = 0; i < n; i++)
    {
        int t = -1;  // 存储当前未加入生成树的节点中距离最小生成树最近的节点
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        if (i && dist[t] == 0x3f3f3f3f) return -1;  // 存在不连通的情况，返回-1
        if (i) res += dist[t];
        st[t] = true;
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);  // 初始化邻接矩阵为无穷大
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if (t == -1) cout << "impossible" << endl;  // 存在不连通的情况，输出impossible
    else cout << t << endl;
    return 0;
}

其中，g[i][j]表示节点i和节点j之间的边权，dist[i]表示节点i到当前生成树的最短距离，st[i]表示节点i是否已经加入生成树。Prim算法的核心部分是选择距离最小生成树最近的节点，通过dist数组维护每个节点到当前生成树的最短距离，并使用st数组判断每个节点是否已经加入生成树。