最小生成树

加油！活成自己喜欢的样子，干嘛要在意别人的眼光。

最小生成树，学了好久了，理论学起来简单易懂，代码一直也没写，今天补起来。

自己太菜了，只能背板子了。

我只是板子的搬运工，哪里需要哪里套。

最小生成树——水题HDU1233

Kruskal

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct node
{
    int x,y;
    int w;
}mp[10000];
int pre[10000];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int find(int x)
{
    if(pre[x]==x)
        return x;
    else
    {
        return pre[x] = find(pre[x]);
    }
    
    
}
void join(int x,int y)
{
    int fx = find(x),fy = find(y);
    if(x!=fy)
    {
        pre[fx] = fy;
    }
}
int main()
{
    while(cin>>n)
    {
        for(int i =1;i<=n;++i)//并查集初始化
            pre[i] = i;
        for(int i =1;i<=n;++i)
        {
            cin>>mp[i].x>>mp[i].y>>mp[i].w;
        }
        int N =(n-1)*n/2;//n个顶点可能共有这些边
        sort(mp+1,mp+1+n,cmp);//kruskal算法从最小边开始
        int k = 0,sum=0;
        for(int i =1;i<=N;++i)
        {
            if(k==n-1)//n个顶点的连通图最少有n-1条边
                break;
            if(find(mp[i].x)!=find(mp[i].y))//判断顶点是否被访问，未访问，则归为一家 join
            {
                k++;
                join(mp[i].x,mp[i].x);
                sum+=mp[i].w;//记录最小距离
            }
        }
        cout<<sum<<endl;

    }
    return 0;
}           

复制

Prim

#include<iostream>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f 
int n;
int mp[10000][10000];
int vis[10000];
int dis[10000];
int ans;
void prim(int n)
{
    for(int i=1;i<=n;++i)
        dis[i] = mp[1][i];
    dis[1] = 0;
    vis[1] = 1;
    for(int i =2;i<=n;++i)
    {
        int t =INF,k;
        for(int j=1;j<=n;++j)
        {
            if(!vis[j]&&dis[j]<t)
            {
                t = dis[j];
                k = j;
            }
        }
        if(t==INF)
            break;
        vis[k] = 1;
        ans+=t;
        for(int j=1;j<=n;++j)
        {
            if(!vis[j]&&dis[j]>mp[k][j])
                dis[j] = mp[k][j];
        }
        
    }
    cout<<ans<<endl;
}
int main()
{
    while(cin>>n&&n)
    {
        ans = 0;
        int m = (n-1)*n/2;
        memset(vis,0,sizeof(vis));
        for(int i =1;i<=m;++i)
        {
            int x,y,w;
            cin>>x>>y>>w;
            mp[x][y] = mp[y][x] = w;
        }
        prim(n);
    }
    return 0;
}           

复制