图论-Prim算法-稠密图

/*
Prim(G,d[])
{
    初始化;
    for(执行n次)
    {
        u=使得d[u]最小且还没有访问的定点的编号;
        记录对u的访问;
        for(从u出发能够到达的所有顶点v) 
        {
            if(v没有访问 && 以u为中介点使得v和集合s的最短距离d[v]更优)
            {
                将G[u][v]赋值给v与集合s的最短距离d[v]; 
            } 
        } 
    } 
}
*/
//邻接矩阵实现
const int MAXV = 1000;
const int INF = 0xFFFFFFF;
int n,G[MAXV][MAXV];
int d[MAXV];
bool vis[MAXV]={false};

int prim()
{
    fill(d,d+MAXV,INF);
    d[0]=0;
    int ans = 0;
    for(int i=0;i<n;i++)
    {
        int u=-1,MIN=INF;
        for(int j=0;j<n;j++)
        {
            if(vis[j]==false && d[j]<MIN)
            {
                MIN=d[j];
                u=j;
            }    
        }
        if(u==-1) return -1;
        vis[u]=true;
        for(int v=0;v<n;v++)
        {
            if(vis[v]==false && G[u][v]!=INF && G[u][v]<d[v])
            {
                d[v]=G[u][v];    
            }    
        }    
    }
    return ans;    
}


//邻接表实现
struct Node{
    int v,dis;
}; 
vector<Node>Adj[MAXV];
int n,d[MAXV];
bool vis[MAXV];
int prim()
{
    fill(d,d+MAXV,INF);
    d[0]=0;
    int ans = 0;
    for(int i=0;i<n;i++)
    {
        int u=-1,MIN=INF;
        for(int j=0;j<n;j++)
        {
            if(vis[j]==false && d[j]<MIN)
            {
                u=j;
                MIN=d[j];
            }
        }
        if(u==-1) return -1;
        vis[u]=true;
        ans += d[u]; 
        for(int j=0;j<Adj[u].size();j++)
        {
            int v = Adj[u][j].v;
            int dis = Adj[u][j].dis;
            if(vis[v]==false && dis<d[v])
            {
                d[v]=dis;
                //ans+=d[v];此处不可以累加 
            }
        } 
    }
}