最小生成树 prim算法

#include<stdio.h>
#include<string.h>
 
#define inf  100000000
#define MAXN 100010
struct edge
{
    int to,w,next;
}x[MAXN];
int head[MAXN];
int cnt;
void add(int u,int v,int w)//建边
{
    x[cnt].to=v;
    x[cnt].w=w;
    x[cnt].next=head[u];
    head[u]=cnt++;
}
bool vis[MAXN];
int n,m;
int low[MAXN];
 
void prim()
{
    int ans=0,j;
    for(int i=1;i<=n;i++)
        low[i]=inf;
    for(int i=head[1];i!=-1;i=x[i].next) //把第一和放进去
        low[x[i].to]=x[i].w;
    memset(vis,0,sizeof(vis));
    int pos=1;
    vis[1]=true;
    for(int i=1;i<n;i++)
    {
        int min_dis=inf,k=-1;
 
        for(int j=1;j<=n;j++) //每次从集合中找到最小的一条边
        {
            if(!vis[j]&&low[j]<min_dis)
            {
                min_dis=low[j];
                k=j;
            }
        }
        if(k==-1)
            return ;
        vis[k]=true;
        printf("%d
",k);
        ans+=min_dis;
        for(int j=head[k];j!=-1;j=x[j].next)//这个数组维护从集合中到这个没有访问过的点的最短距离
        {
            if(!vis[x[j].to]&&x[j].w<low[x[j].to])
                low[x[j].to]=x[j].w;
        }
    }
    printf("%d
",ans);
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        prim();
    }
    return 0;
}
/*
3 3
1 2 2
1 3 3
2 3 3
 
*/