首页 / 算法 / 最小生成树之 prim算法和kruskal算法(以 hdu 1863为例)

最小生成树之 prim算法和kruskal算法(以 hdu 1863为例)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最小生成树之 prim算法和kruskal算法(以 hdu 1863为例)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2927字，纯文字阅读大概需要5分钟。

内容图文

最小生成树的性质

MST性质：设G = (V,E)是连通带权图，U是V的真子集。如果(u,v)∈E,且u∈U,v∈V-U,且在所有这样的边中，

(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，(u,v)为其中一条边。

构造最小生成树，要解决以下两个问题：
(1).尽可能选取权值小的边，但不能构成回路（也就是环）。
(2).选取n-1条恰当的边以连接网的n个顶点。

Prim算法的思想：

设G = (V,E)是连通带权图，V = {1,2,…,n}。先任选一点（一般选第一个点），首先置S = {1}，然后，只要S是V的真子集，就选取满足条件i ∈S,j ∈V-S,且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S = V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

 

Prim 算法代码     

以 hdu 1863为例 （点击打开链接） 

#include<stdio.h>
#include<limits.h>
#include<string.h>
#define N 100
int n,m,map[N+5][N+5],v[N+5],low[N+5];
int prim()
{
    int i,j,pos,min,s=0;
    memset(v,0,sizeof(v));           //v[i]用来标记i是否已访问，先初始化为0，表示都未访问
    v[1]=1;                         //先任选一点作为第一个点
    pos=1;                          //pos用来标记当前选的点的下标for(i=2;i<=n;i++)
        low[i]=map[1][i];          //用low数组存已选点到其他点的权值for(i=1;i<n;i++){
        min=INT_MAX;
        for(j=1;j<=n;j++)                //求权值最小的边if(!v[j]&&low[j]<min){
                min=low[j];
                pos=j;                 
            }
        if(min==INT_MAX)    
            break;
        s+=min;            
        v[pos]=1;           
        for(j=1;j<=n;j++)                   //更新low数组    if(!v[j]&&map[pos][j]<low[j])
                low[j]=map[pos][j];
    }
    if(i!=n)
        s=-1;
    return s;
}
int main()
{
    int i,j,s,a,b,c;
    while(scanf("%d%d",&m,&n)!=EOF){          //m为道路数，n为村庄数if(m==0)
            break;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                map[i][j]=INT_MAX;             //先将map数组初始化为很大的值（int 最大值）for(i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]=map[b][a]=c;             //map[a][b]存的从a到b的权值        }
        s=prim();
        if(s==-1)
            printf("?\n");
        else
            printf("%d\n",s);
    }
    return0;
}
View Code

 

Kruskal算法思想

给定无向连同带权图G = (V,E),V = {1,2,...,n}。

（1）首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小大排序。

（2）从第一条边开始，依边权递增的顺序检查每一条边。并按照下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2的端点是，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看k+1条边。这个过程一个进行到只剩下一个连通分支时为止。 此时，已构成G的一棵最小生成树。

Kruskal 算法代码：

以 hdu 1863为例 （ 点击打开链接 ） 

                 1 #include<cstdio>
 2 #include<algorithm>
 3usingnamespace std;
 4int f[105],n,m;
 5struct stu
 6{
 7int a,b,c;
 8 }t[5500];
 9int cmp(struct stu x,struct stu y)
10{
11return x.c<y.c;
12}
13int find(int x)              //路径压缩，找父节点14{
15if(x!=f[x])
16         f[x]=find(f[x]);
17return f[x];
18}
19int krus()
20{
21int i,k=0,s=0,x,y;
22for(i=1;i<=n;i++){
23         x=find(t[i].a);
24         y=find(t[i].b);
25if(x!=y){              //最小生成树不能形成环，所以要判断它们的是否属于同一集合26             s+=t[i].c;
27             k++;
28if(k==m-1)      //<span style="font-family: KaiTi_GB2312;">最小生成树会形成m-1（顶点-1）条边，若已形成，则最小生成树已构成</span>29break;
30             f[x]=y;          //将父节点更新31        }
32    }
33if(k!=m-1)
34         s=-1;
35return s;
36}
37int main()
38{
39int i,s;
40while(scanf("%d%d",&n,&m)!=EOF){
41if(n==0)
42break;
43for(i=1;i<=n;i++)
44             scanf("%d%d%d",&t[i].a,&t[i].b,&t[i].c);
45for(i=1;i<=m;i++)         //f[i]存的结点i的父亲，先将其父亲都初始化为其本身46             f[i]=i;
47         sort(t+1,t+1+n,cmp);      //按权值从小到大排序48         s=krus();
49if(s==-1)
50             printf("?\n");
51else52             printf("%d\n",s);
53    }
54return0;
55 }
View Code

 

 

注：若顶点数为n,边为e

prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边的数目无关，

而 kruskal 算法的时间复杂度为 O(eloge)跟边的数目有关，适合稀疏图。



原文：http://www.cnblogs.com/happy-lcj/p/3855407.html

内容总结

以上是互联网集市为您收集整理的最小生成树之 prim算法和kruskal算法(以 hdu 1863为例)全部内容，希望文章能够帮你解决最小生成树之 prim算法和kruskal算法(以 hdu 1863为例)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1226265.html

来源：【匿名】