prime算法最小生成树

‘壹’ prime算法什么意思

prime？如果真的是prime的话，那可能是指打素数表的方法。比如欧拉筛法之类的。
如果是prim算法的话，是一种贪心的最小生成树算法。

‘贰’ primt算法求无向网的最小生成树c++程序

网上一大把啊。。

我告诉你思路吧，prime算法是贪心策略，每次选出可以连通的最短边，直到生成树形成

‘叁’ prime算法建立最小生成树的代码

这个我也不会,

‘肆’ 13.用Prim算法和Kruskal算法构造图的最小生成树,所得到的最小生成树是否相同

如果原来的图里面任何两条边长都不相同,那么最小生成树是唯一的,此时不管用什么方法算出来的都是一样的
但是如果图里有相等的边,那么最小生成树可能会不唯一,这样就无法保证不同的方法得到同一棵树（即使是同一个算法,只要图的编号方式改变也可能得到不同的最小生成树）

‘伍’ 杭电acm1233

同学，这个就是赤裸裸的最小生成树算法。prime算法和kruskal算法都可以顺利通过，没有一点陷阱。建议你用kruskal算法来解。在学习kruskal算法之前，学习一下并查集。这个问题一点也不难。
这里给出sruskal算法的解：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

int pre[105];

struct node
{
int x1,x2;
int cost;
}D[5050];

void Init(int n)
{
int i;
for(i=1;i<=n;i++)
pre[i]=i;
}

int Find(int x)
{
int t,r=x;
while(x!=pre[x]) x=pre[x];
while(r!=x)
{
t=pre[r];
pre[r]=x;
r=t;
}
return x;
}

void Union(int a,int b)
{
a=Find(a);
b=Find(b);
pre[b]=a;
}

bool cmp(node a,node b)
{
return a.cost<b.cost;
}

int main()
{
int n,t,i,cnt,ans;
while(scanf("%d",&n)!=EOF,n)
{
Init(n);
t=n*(n-1)/2;
for(i=0;i<t;++i)
scanf("%d%d%d",&D[i].x1,&D[i].x2,&D[i].cost);
sort(D,D+t,cmp);
cnt=1;i=0;ans=0;
while(cnt<n&&i<t)
{
if(Find(D[i].x1)!=Find(D[i].x2))
{
++cnt;
Union(D[i].x1,D[i].x2);
ans+=D[i].cost;
}
++i;
}
printf("%d\n",ans);
}
return 0;
}

kruskal算法的思路你可以在维基网络上找到，至于并查集，你可以看我的笔记http://whchen.net/blog/?p=259
这道题所有代码就包含排序和并查集而已，没什么太复杂的，加油！

‘陆’ 分别给出下图使用Prime算法（从A开始）和kruskar找最小支撑树的过程

最小生成树：
Prime：从某点开始每次找邻接的最小边，忽略已经加入的顶点
AB，AD，DE，DC，DF
Kruskar：每次从剩余边集合里找最小边，忽略已经加入的顶点
DE，AB，DC，AD，DF
两者是一样的，顺序不同而已

‘柒’ C语言中prime的作用

prime的作用就是判断一个数是否为素数（也称“质数”）。

例如：

#include<stdio.h>

intIsPrime(intn)

{

if(n<=1)return0;

if(n%2==0)returnn==2;

for(inti=3;;i+=2)

{

if(i>n/i)break;//等价于i*i>n,不用开方

if(n%i==0)return0;

}

return1;

}

intmain()

{

for(intn=100;n<=300;n++)

if(IsPrime(n))

printf("%4d",n);

return0;

}

(7)prime算法最小生成树扩展阅读：

prime算法

prime是以点为基础出发进行检索最小生成树的一种贪心算法。

思想：

将所有的点分成两类，一类是已经放到碗里的，另一类是还没有有放到碗里的，可以通过一个数组bool visit[]来记录这个点到底是属于第一类还是属于第二类之后每一个周期索要进行的操作，找出一一定范围内路径的的范围的最小值。

所有的从第一类点直接连接到第二类点的边将最小的边记录下来（这个也就是生成树中的一条边）将这个新边（这个一个连接第一类点和第二类点的边）连到的那个第二类点归类到第一类点中，之后重复这个操作，最终消灭所有的第二类点。

假设有n个节点，我最初给出一个点，以这个点开始进行搜索，这个时候该点为第一类点，其余n-1个点为第二类点。之后进行n-1次操作，一共选出了n-1个边（符合树的性质），构成了最小生成树。

‘捌’ 啊，求教prime算法中我这个二维数组咋输入

将一个图的顶点分为两部分，一部分是最小生成树中的结点（A集合），另一部分是未处理的结点（B集合）。
2.首先选择一个结点，将这个结点加入A中，然后，对集合A中的顶点遍历，找出A中顶点关联的边权值最小的那个（设为v），将此顶点从B中删除，加入集合A中。
3.递归重复步骤2，直到B集合中的结点为空，结束此过程。
4.A集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤2的结点连接这些顶点，得到的就是这个图的最小生成树。