代码与Dijkstra相似

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

const int maxv =510;
const int INF = 1000000000;
int n, G[maxv][maxv];
int d[maxv];
bool vis[maxv] = {false};

struct Node
{
    int v;
    int dis;
};
vector<Node> Adj[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++)
        {
            u = j;
            MIN = d[j];
        }
    }
    if(u == -1)
        return;

    vis[u] = true;
    ans += d[u];
    for (int v = 0; v < n; v++)
    {
        if(vis[v] == false && G[u][v] < MIN)
        {
            d[v] = G[u][v];
        }
    }
    return ans;
    
}


int prim2()
{
    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;
        
        vis[u] = true;
        ans += d[u];
        for (int j = 0; j < n; j++)
        {
            int v = Adj[u][j].v;
            int dis = Adj[u][j].dis;
            if(vis[v] == false && dis < d[v])
            {
                d[v] = dis;
            }
        }
    }
    return ans;
}