首页 > 代码库 > 最小生成树算法汇总 （普里姆 && 克鲁斯卡尔与并查集结合）

最小生成树算法汇总 （普里姆 && 克鲁斯卡尔与并查集结合）

2024-07-06 17:04:42   223人阅读

最小生成树：


今天研究了一下最小生成树，感觉最小生成树算法与最短路算法 相差不大，从Prim 与 Dijskrs算法可以看出


最小生成树即最小权重生成树，主要适用于 N个点之间 构造N-1线路，使N个点之间任意两点之间都可到达，
但是N个点之间 不构成回路，并且这N-1条线路的权重之和最小即 消耗最小。


注意：在构造最小生成树，加入新的节点时，不仅要保证权重最小，首要条件是 不能构成回路。


以图示为例，构造最小生成树


（一）普里姆   以下步骤



（二） 克鲁斯卡尔 最终的最小生成树 和 普里姆一样  




   一、普里姆算法  
       
       思想：取图中任意一点，以确定当前点所连接所有点的权重中最小的点来加入最小生成树，再以新加入

的点，来继续确定剩余点到当前点的权重最小加入最小生成树


时间复杂度：O(n*n)

适应范围   :  稠密图


const int N = 65535;
int map[1000][1000];
int vis[1000],dis[1000];
void prim()
{
   
    int ans=0;
    int i,j;
    memset(vis,0,sizeof(vis)); //标记是否被访问的数组，初始化
    memset(dis,0,sizeof(dis));
    for(i = 1; i <= n; i++)
        dis[i] = map[1][i];    //dis[]保存到最小生成树的最短距离
    vis[1] = 1; //标记1顶点已加入最小生成树
    for(i = 1; i <= n-1; i++)
    {
        int pos;//寻找一个未被加入生成树的点，满足它到生成树的距离最短
        int min; //保存这个最短距离
        min = N;
        for(j = 1; j <= n; j++)
        {
            if(vis[j]==0&&min>dis[j])
            {
                pos=j;
                min=dis[j];
            }
        }
         if(min==N)
         {
           printf("?\n");//如果没有点相连，打印问号
            return ;
         }
        vis[pos]  = 1; //标记已加入最小生成树集合...
        ans += min;    //权值加上那个最短距离
        for(j = 1; j <= n; j++) //松弛，因为pos的加入，其他点到最小生成树的//距可能减小
        {
            if(vis[j]==0 && dis[j]>map[pos][j])
                dis[j]=map[pos][j];
        }
    }
     printf("%d\n",ans);
        return ;
}



   二、克鲁斯卡尔
     
       思想：以确定边来构造最小生成树，当然克鲁斯卡尔应用的是贪心思想+并查集，按权值递增顺序删去图中的边，

若不形成回路则将此边加入最小生成树


时间复杂度 :   O(e*loge)

适应范围   ：   稀疏图


具体操作：  1。并查集 合并操作，2、将权重 排序，3、构造最小生成树


事例代码：

         n个城市，m条线路，修建n-1 条路使任意一点都可以到达所有城市，并且话费最少

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
const int N = 65535;
using namespace std;
struct node{
    int u,w,v;
}edge[10001];
int father[1001],n,m,ans;
int cmp(const void *a,const void *b)
{
    node *X,*Y;
    X = (struct node *)a;
    Y = (struct node *)b;

    return X->w - Y->w ;
}
int find(int r)//2查找
{
    return (father[r]==r)?r:find(father[r]);
}

void merge(int x,int y)//3合并
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
        father[fx] = fy;
}

void init()
{
    for(int i = 1; i <= n; i++)
        father[i] = i;	//每个节点初始化自成一个集合
}
void kruskal()
{
    init();
    for(int i = 0; i < m; i++)	//按边的权值大小加边
    {
        //找当前点到最小生成树的最短边
        int uu = find(edge[i].u);
        int vv = find(edge[i].v);
        if(uu != vv)
        {
            father[uu] = vv;
            ans += edge[i].w;
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        ans = 0;
        for(int i =0;i<m;i++)
        {
            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
            merge(edge[i].u,edge[i].v);
        }

        qsort(edge,m,sizeof(edge[0]),cmp);//升序排序
        kruskal();

        printf("%d\n",ans);
    }
    return 0;
}





联系
我们