最小生成树 prim kruscal

prim算法：

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 0x7fffffff
using namespace std;
int dis[200][200],vis[200],low[200],n,m;
int prim()
{
    int i,j,sum=0,pos=1;
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    for(i=1; i<=n; i++)
        low[i]=dis[1][i];
    low[1]=0;
    for(j=1;j<n;j++)
    {
        int min=MAX;
        for(i=1; i<=n; i++)
            if(!vis[i]&&low[i]<min)
            {
                min=low[i];
                    pos=i;
            }
            if(min==MAX)break;
            vis[pos]=1;
            sum+=min;
            for(i=1;i<=n;i++)
            if(!vis[i]&&low[i]>dis[pos][i])
            low[i]=dis[pos][i];

    }
    return sum;
}

int main()
{
    int i,j,a,b,t;
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            dis[i][j]=MAX;
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&a,&b,&t);
        if(t<dis[a][b])dis[a][b]=dis[b][a]=t;
    }
    printf("%d\n",prim());
    return 0;
}

最小生成树 prim kruscal,布布扣,bubuko.com

最小生成树 prim kruscal

原文：http://blog.csdn.net/fei____fei/article/details/22205309