最小生成树 get ！

A4paper · 2018-04-20 20:28:16 · 个人记录

prim:

bool vis[100];
long dis[100];

void prim()
{
long minn,point;
    memset(dis,0x3f,sizeof(dis));
    dis[1] = 0; //一定要记得将根节点赋0
    for(long i=1;i<=m;i++)
    {
        minn = 0x3f3f3f;
        for(long j=1;j<=m;j++)
            if(!vis[j] && minn>dis[j])
            {
                minn = map[j];
                point = j;
            }
        vis[point] = 1;
        for(long j=1;j<=m;j++)
            if( dis[j] > map[point][j] && !vis[j])
                dis[j] = map[point][j];
    }
}

kruskal:

long n,m;
long parent[100];

//用kruskal时要存储边，u,v,是两头结点
struct node 
{
    long u,v,w;
}map[100];

long cmp(node a,node b)
{
    return a.w < b.w;
}

//***********************并查集***************************
long find(long x)
{
    if(parent[x] == x)  return x;
    return parent[x] = find(prn[x]);
}

void  Union(long x,long y)
{
    int t1 = find(x);
    int t2 = find(y);
    if(t1 != t2) parent[t1] = t2;
}
//*******************************************************

void kruskal()
{
long count = 0;
    for(int i=1;i<=m;i++)   parent[i] = i;
    sort(map+1,map+n+1,cmp);

    for(int i=1;i<=n;i++)
        if (find(map[i].u) != find(map[i].v))
        {
            Union(map[i].u,map[i].v);
            if(++count == m-1)  break;
        }
}

}
long main()
{
    cin >> m >> n;
    for (long i=1;i<=n;i++) //存图方式略有不同
    {
long v,u,w;
        cin >> v >> u >> w;
        map[i].v = v; 
        map[i].u = u;
        map[i].w = w;
    }
    kruskal();
    return 0;
}