最小生成树(次小生成树)(最小生成树不唯一) 模板：Kruskal算法和 Prim算法

Kruskal模板：按照边权排序，开始从最小边生成树

#include<algorithm>

#include<stdio.h>

#include<string.h>

#include<iostream>

#define N 1000+5//n 个顶点，m条边

using namespace std;

//最小生成树模板(计算最小生成树的sum)

struct node

{

    int u,v,len;//u->v距离len

}q[N];

int f[N],n,m;

int getf(int v)

{

    if(f[v]==v)

        return v;//找到祖先

    return f[v]=getf(f[v]);//压缩路径

}

bool marge(int u,int v)

{

    int t1=getf(u),t2=getf(v);

    if(t1==t2)

        return 0;//同一个祖先，已经连接过

    f[t1]=t2;

    return 1;

}

bool comp(node a,node b)

{

    return a.len<b.len;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=0;i<=n;i++)//初始化并查集数组

        f[i]=i;//祖先是本身

    for(int i=0;i<m;i++)

        scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].len);

    sort(q,q+m,comp);//按照边的权值从小到大排序

    int count=0,sum=0;

    for(int i=0;i<m;i++)

    {

        if(count==n-1)//n个顶点 n-1条边

            break;

        if(marge(q[i].u,q[i].v))

        {

            count++;

            sum+=q[i].len;

        }

    }

    if(count==n-1)

        printf("%d\n",sum);

    else

        printf("NO\n");

    return 0;

}

Prim模板：找树顶点和非树顶点之间的最小边

1、邻接矩阵

//prim算法

#include<stdio.h>

#include<string.h>

#define N 100+5

int main()

{

    int n,m,e[N][N],dis[N];

    bool book[N];

    scanf("%d%d",&n,&m);

    memset(dis,0x3f3f3f3f,sizeof(dis));

    memset(e,0x3f3f3f3f,sizeof(e));

    memset(book,0,sizeof(book));

    for(int i=0;i<N;i++)

        e[i][i]=0;//邻接矩阵

    int u,v,len;

    for(int i=0;i<m;i++)

    {

        scanf("%d%d%d",&u,&v,&len);

        e[v][u]=e[u][v]=len;

    }

    for(int i=1;i<=n;i++)

        dis[i]=e[1][i];//初始化dis数组

    /* prim核心 */

    book[1]=1;//标记树顶点

    int count=1,sum=0;//已经加入树的顶点

    while(count<n)//知道顶点全部是树顶点

    {

        int minn=0x3f3f3f3f,j;

        for(int i=1;i<=n;i++)//找到树顶点与非树顶点之间最短的边

        {

            if(dis[i]<minn&&!book[i])

                j=i,minn=dis[i];

        }

        sum+=minn;

        count++;

        book[j]=1;

        for(int i=1;i<=n;i++)//遍历更新树顶点和非树顶点之间的最短路径

        {

            if(!book[i]&&dis[i]>e[j][i])

                dis[i]=e[j][i];

        }

    }

    printf("%d\n",sum);

    return 0;

}

2、邻接表

次小生成树：

当给我们求出最小生成树的时候，依次将不属于最小生成树的边（u,v）加入生成树中，此时形成一个环，找出这个环中除了(u,v)最大的边删除,得出的可能是次小生成树，列举所有边，求出次小值.

最小生成树不唯一：

输入边的时候记录一下权值相等的边，求最小生成树，判断边是否被标记，如果被标记，依次删除，看是否能生成最小生成树，如果可以，则最小生成树不唯一。poj - 1679

巴特西

最小生成树(次小生成树)(最小生成树不唯一) 模板：Kruskal算法和 Prim算法

最新文章

热门文章