Prim算法求最小生成树

1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边[HTML_REMOVED]，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将[HTML_REMOVED]边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。

时间复杂度 $O(n^2+m)$

Prim算法和Dijkstra算法都是基于贪心的思想，写法上也很类似

C++ 代码

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

const int N = 101;
int g[N][N];
int dist[N];
int st[N];
int n;

int prim(){
    int ans = 0;
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 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(dist[t]==0x3f3f3f3f) return 0x3f3f3f3f;  //若图不连通，返回（本题不需要）
        for(int j=1; j<=n; j++)
            dist[j] = min(dist[j], g[t][j]);  //更新
        st[t] = 1;
        ans += dist[t];  
    }
    return ans;
}

int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++)cin>>g[i][j];
    }
    cout<<prim();
    return 0;
}