最小生成树模板（Prim+Kruskal）

一：Prim算法

void prim(int src)//prim算法是根据点来连接的寻找n-1个点
{
    int i,j,k,tmp;
    ll sum=0;
    for(i=1;i<=n;++i)
        dis[i]=mt[1][i],vis[i]=0;//初始化距离,标记清0
    vis[1]=1;dis[1]=0;
    for(i=0;i<n-1;++i){
        tmp=INF;
        for(j=1;j<=n;++j)
            if(!vis[j]&&dis[j]<tmp)//找到最短距离-连接两点
            tmp=dis[j],k=j;
//        if(tmp==INF) break;
        vis[k]=1;
        sum+=(ll)tmp;
        for(j=1;j<=n;++j)
            if(!vis[j]&&dis[j]>mt[k][j])//连接两点后更新已连点和未连点间最短距离
            dis[j]=mt[k][j];
    }
    cout<<sum<<endl;
}

二：Kruskal算法

struct node{
    int val;
    int start;
    int end;
}edge[maxn];

void make_set()//初始化集合，让所有的点都各成一个集合，每个集合都只包含自己
{
    for (int i=1;i<=n;i++)
    father[i] = i;
//    cap[i] = 1;
}

int Find(int x)
{
    if(x!=father[x]){
        father[x]=Find(father[x]);
    }
    return father[x];
}

void Union(int x,int y)
{
    x=Find(x);y=Find(y);
    if(x!=y) father[x]=y;
}

int Kruskal(int n)
{
    int sum = 0;
    make_set();
    for (int i=1;i<=n;i++)//将边的顺序按从小到大取出来
    {
        if (Find(edge[i].start)!=Find(edge[i].end)) //如果改变的两个顶点还不在一个集合中，就并到一个集合里，生成树的长度加上这条边的长度
        {
            Union(edge[i].start, edge[i].end);  //合并两个顶点到一个集合
            sum += edge[i].val;
        }
    }
    return sum;
}

注意Krustal先要对边进行排序

prim例题：最小生成树一·Prim算法

#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define mem(a,b) memset(a,b,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;
using namespace std;
const int maxn=1010;
int mt[maxn][maxn],vis[maxn],dis[maxn];
int n;

void prim(int src)
{
    int i,j,k,tmp;
    ll sum=0;
    for(i=1;i<=n;++i)
        dis[i]=mt[1][i],vis[i]=0;
    vis[1]=1;dis[1]=0;
    for(i=0;i<n-1;++i){
        tmp=INF;
        for(j=1;j<=n;++j)
            if(!vis[j]&&dis[j]<tmp)
            tmp=dis[j],k=j;
//        if(tmp==INF) break;
        vis[k]=1;
        sum+=tmp;
        for(j=1;j<=n;++j)
            if(!vis[j]&&dis[j]>mt[k][j])
            dis[j]=mt[k][j];
    }
    cout<<sum<<endl;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        cin>>mt[i][j];
    prim(1);
}

Kruskal例题：最小生成树二·Kruscal算法

typedef long long ll;
using namespace std;
const int maxn=1e6+10;
int n,m;
int a[maxn][2],father[maxn],cap[maxn];
struct node
{
    int x,y;
    int val;
}edge[maxn];
bool cmp(node a,node b)
{
    return a.val<b.val;
}
void make_set(int n)
{
    for(int i=1;i<=n;++i)
        father[i]=i,cap[i]=1;
}

int Find(int x)
{
    if(x!=father[x]){
        father[x]=Find(father[x]);
    }
    return father[x];
}

int Union(int x,int y)
{
    x=Find(x),y=Find(y);
    if(x==y)
        return 0;
    if(cap[x]<cap[y])
        father[x]=y;
    else{
        if(cap[x]==cap[y])
            cap[x]++;
        father[y]=x;
    }
    return 1;
}

int main()
{
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i){
            scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].val);
        }
        sort(edge+1,edge+m+1,cmp);
        int ans=0;
        int sum=0;
        make_set(n);
        for(int i=1;i<=m;++i){
            if(Union(edge[i].x,edge[i].y)){
                ++ans;
                sum+=edge[i].val;
            }
            if(ans==n-1) break;
        }
        printf("%d
",sum);

}

放一个久远的神仙模板：

#include<iostream>
#define N 7
using namespace std;
typedef struct _node{
    int val;
    int start;
    int end;
}Node;
Node V[N];
int cmp(const void *a, const void *b)
{
    return (*(Node *)a).val - (*(Node*)b).val;
}
int edge[N][3] = {  { 0, 1, 3 },
                    { 0, 4, 1 }, 
                    { 1, 2, 5 }, 
                    { 1, 4, 4 },
                    { 2, 3, 2 }, 
                    { 2, 4, 6 }, 
                    { 3, 4, 7} 
                    };
 
int father[N] = { 0, };
int cap[N] = {0,};
 
void make_set()              //初始化集合，让所有的点都各成一个集合，每个集合都只包含自己
{
    for (int i = 0; i < N; i++)
    {
        father[i] = i;
        cap[i] = 1;
    }
}
 
int find_set(int x)              //判断一个点属于哪个集合，点如果都有着共同的祖先结点，就可以说他们属于一个集合
{
    if (x != father[x])
     {                              
        father[x] = find_set(father[x]);
    }     
    return father[x];
}                                  
 
void Union(int x, int y)         //将x,y合并到同一个集合
{
    x = find_set(x);
    y = find_set(y);
    if (x == y)
        return;
    if (cap[x] < cap[y])
        father[x] = find_set(y);
    else
    {
        if (cap[x] == cap[y])
            cap[x]++;
        father[y] = find_set(x);
    }
}
 
int Kruskal(int n)
{
    int sum = 0;
    make_set();
    for (int i = 0; i < N; i++)//将边的顺序按从小到大取出来
    {
        if (find_set(V[i].start) != find_set(V[i].end))     //如果改变的两个顶点还不在一个集合中，就并到一个集合里，生成树的长度加上这条边的长度
        {
            Union(V[i].start, V[i].end);  //合并两个顶点到一个集合
            sum += V[i].val;
        }
    }
    return sum;
}
int main()
{
    for (int i = 0; i < N; i++)   //初始化边的数据，在实际应用中可根据具体情况转换并且读取数据,这边只是测试用例
    {
        V[i].start = edge[i][0];
        V[i].end = edge[i][1];
        V[i].val = edge[i][2];
    }
    qsort(V, N, sizeof(V[0]), cmp);
    cout << Kruskal(0)<<endl;
}