Prim算法 最小生成树问题
- Prim算法 最小生成树问题
- 求一个学过数据结构（C语言版）的大神，有一个关于克鲁斯卡尔算法和普里姆算法的问题！
- 最小生成树 普里姆算法和克鲁斯卡尔算法
- 普里姆算法是什么
- 普利姆 克鲁斯卡尔 算法 哪个更快
你的图里有两条边权重一样，在实际计算前无法事先保证最小生成树的唯一性，即使是两个不同的Prim算法也可能产生不同的结果
当然，计算完之后情况会略有不同，下面会解释
Prim算法首先会依次选
E(1,2)=1
E(2,7)=2
E(2,3)=3
然后E(3,4)=E(7,6)=4，会面临两种选择
如果优先选E(3,4)这条边，那么下一步仍然会选E(7,6)，反过来也一样，所以这个图恰好没影响
继续下去最终得到
E(1,2)=1
E(2,7)=2
E(2,3)=3
E(3,4)=4
E(7,6)=4
E(4,5)=6
这样6条边构成唯一的最小生成树，总权重是20
（唯一性是因为总权重不超过20的其它子图确实都不连通）
既然最小生成树唯一，Kruskal算法当然也会产生同一棵树
克鲁斯卡尔和prime算法都是最小生成树的贪心算法，可以证明其拥有最优解结构。证明简单的可以参考wiki，要严格证明请参考算法导论和计算机程序设计的艺术中的相关内容。由于其相关论文比较久远，我也不建议你去查了。
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.baidu.com/valyanprogramming/blog/item/1bc960e6095f9726b93820d9.html
1.Kruskal
//题目地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1258
#include《cstdio》
#include《cstdlib》
#include《iostream》
using namespace std;
struct node
{
int v1;
int v2;
int len;
}e;//定义边集
int cmp(const void *a,const void *b)//快排比较函数
{
return ((node*)a)-》len-((node*)b)-》len;
}
int v;//v为点集
void makeset(int n)
{
for(int i=0;i《n;i++)
v=i;
}
int find(int x)
{
int h=x;
while(h!=v)
h=v;
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);
e.v1=i;
e.v2=j;
e;
p++;
}
}
qsort(e,p,sizeof(e),cmp);
for(i=0;i《p;i++)
{
r1=find(e.v1);
r2=find(e.v2);
if(r1!=r2)
{
total+=e.len;
v=r2;
}
}
printf(“%d
“,total);
}
system(“pause“);
return 0;
}
2.Prim
//题目地址同上
#include 《iostream》
using namespace std;
#define M 101
#define maxnum 100001
int dis;
int prim(int n)
{
bool used={};
int d,i,j,k;
for(i=1; i《=n; i++)
d;
used = true;
int sum=0;
for(i=1; i《n; i++){
int temp=maxnum;
for(j=1; j《=n; j++){
if( !used《temp ){
temp = d;
k = j;
}
}
used = true;
sum += d;
for(j=1; j《=n; j++){
if( !used )
d; // 与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);
if( !dis )
dis = maxnum;
}
}
cout《《prim(n)《《endl;
}
return 0;
}
代码来自网络
普里姆(Prim)算法，和克鲁斯卡尔算法一样，是用来求加权连通图的最小生成树的算法。
普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。
该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
基本思想：
对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。?
从所有u?U，v?(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。
在不使用优先队列优化时，普里姆的时间复杂度是O（V ^2) ）的,使用后是O(Elog(V))的。
而快排克鲁斯卡尔是 O（E log (V)）的,
也就是时间复杂度是一样的。
如果你会用费波那契堆，PRIM的效率会有一定的提升。
相关tag:克鲁斯卡尔和普里姆结果一样吗
本站部分资源来源于网络，如果侵犯了您的权益，请联系我们删除1354090129@qq.com