导航:首页 > 源码编译 > prim算法和kruskal算法的区别

prim算法和kruskal算法的区别

发布时间:2023-09-25 07:17:04

❶ 最小生成树两种算法有何区别

主要有两个:
1.普里姆(Prim)算法

特点:时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔(Kruskal)算法

特点:时间复杂度为O(eloge)(e为网中边数),适合于求稀疏的网的最小生成树。

❷ prim和kruscal算法得到的最小生成树是否一样

应该不一样。可以用一个图根据两算法试一下,若一样,再修改图,之后应该就可以了。
(网络或者查书本更加有效……)
构造G的最小生成树的Prim算法的基本思想是:首先置S={1},然后,只要S是V的真子集,就作如下的贪心选择:选取满足条件iS,jV-S,且c[i][j]最小的边,将顶点j添加到S中。
这个过程一直进行到S=V时为止。
Kruskal算法构造G的最小生成树:将所有的边按权从小到大排序。然后从第一条边开始,依边权递增的顺序查看每一条边,并按下述方法连接2个不同的连通分支:当查看到第k条边(v, w)时,如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时,就用边(v, w)将T1和T2连接成一个连通分支,然后继续查看第k+1条边;如果端点v和w在当前的同一个连通分支中,就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止

❸ 最小生成树 普里姆算法和克鲁斯卡尔算法

kruskal算法的时间复杂度主要由排序方法决定,其排序算法只与带权边的个数有关,与图中顶点的个数无关,当使用时间复杂度为O(eloge)的排序算法时,克鲁斯卡算法的时间复杂度即为O(eloge),因此当带权图的顶点个数较多而边的条数较少时,使用克鲁斯卡尔算法构造最小生成树效果最好!

克鲁斯卡尔算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止。

普里姆算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,TV 是 WN 上最小生成树中顶点的集合,TE 是最小生成树中边的集合。显然,在算法执行结束时,TV=V,而 TE 是 E 的一个子集。在算法开始执行时,TE 为空集,TV 中只有一个顶点,因此,按普里姆算法构造最小生成树的过程为:在所有“其一个顶点已经落在生成树上,而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边,逐条加在生成树上,直至生成树中含有 n-1条边为止。
--以上传自http://hi..com/valyanprogramming/blog/item/1bc960e6095f9726b93820d9.html

1.Kruskal
//题目地址:http://acm.pku.e.cn/JudgeOnline/problem?id=1258

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node
{
int v1;
int v2;
int len;
}e[10000];//定义边集
int cmp(const void *a,const void *b)//快排比较函数
{
return ((node*)a)->len-((node*)b)->len;
}
int v[100],a[100][100];//v为点集
void makeset(int n)
{
for(int i=0;i<n;i++)
v[i]=i;
}
int find(int x)
{
int h=x;
while(h!=v[h])
h=v[h];
return h;
}
int main()
{
int n,i,j,r1,r2,p,total;
while(scanf("%d",&n)!=EOF)
{
p=0;
total=0;
makeset(n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
e[p].v1=i;
e[p].v2=j;
e[p].len=a[i][j];
p++;
}
}
qsort(e,p,sizeof(e[0]),cmp);
for(i=0;i<p;i++)
{
r1=find(e[i].v1);
r2=find(e[i].v2);
if(r1!=r2)
{
total+=e[i].len;
v[r1]=r2;
}
}
printf("%d\n",total);
}
system("pause");
return 0;
}

2.Prim
//题目地址同上

#include <iostream>
using namespace std;

#define M 101
#define maxnum 100001
int dis[M][M];

int prim(int n)
{
bool used[M]={};
int d[M],i,j,k;
for(i=1; i<=n; i++)
d[i] = dis[1][i];
used[1] = true;
int sum=0;
for(i=1; i<n; i++){
int temp=maxnum;
for(j=1; j<=n; j++){
if( !used[j] && d[j]<temp ){
temp = d[j];
k = j;
}
}
used[k] = true;
sum += d[k];
for(j=1; j<=n; j++){
if( !used[j] && dis[k][j]<d[j] )
d[j] = dis[k][j]; // 与Dijksta算法的差别之处
}
}
return sum;
}

int main()
{
int n,i,j;
while( cin>>n ){

for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d",&dis[i][j]);
if( !dis[i][j] )
dis[i][j] = maxnum;
}
}

cout<<prim(n)<<endl;
}
return 0;
}

代码来自网络

❹ 普里姆算法和克鲁斯卡尔算法区别

普里姆算法和克鲁斯卡尔算法区别如下:
克鲁斯卡尔算法:是在剩下的所有未选取的边中,找最小边,如果和已选取的边构埋或成回路,则放弃,选晌液宴取次小边。
普里姆算法:同样是在未选取的边中寻找最小边,但是选取的原则多了宴银一条,就是该边必须和已选取的边相连,比如,如果边(1, 2)已被选取,那么接下来选取的边,必须是和顶点1,或者顶点2相连的。

阅读全文

与prim算法和kruskal算法的区别相关的资料

热点内容
腾讯云服务器ssh密钥 浏览:43
帮帮通app哪里下载 浏览:437
仪器仪表app下载存在哪里 浏览:726
javadate相减 浏览:381
英飞凌单片机开发环境 浏览:214
圆周铣怎么编程序 浏览:563
linux静态路由永久 浏览:275
源码家族 浏览:855
小程序源码搭建在网站 浏览:16
javatcp文件 浏览:933
哪咤汽车app哪里下载 浏览:535
公交车间隔加密线路 浏览:799
网格加密清洁巾生产厂家 浏览:273
淘特app每周领东西在哪里 浏览:244
ip地址和域名之间转换工作的是什么服务器 浏览:205
西门子编程软件不能转换中文 浏览:831
linux服务器调优 浏览:257
web服务器怎么搭配 浏览:189
做交友APP去哪里引流 浏览:552
什么赚钱的APP 浏览:900