若从顶点u0=a开始使用普里姆（Prim）算法计算下列无向网的最小生成树？
- 用普里姆(Prim)算法求出下图的最小生成树。
- 最小生成树 普里姆算法和克鲁斯卡尔算法
- 设某带权无向图如下图，画出用Prim算法，从顶点A开始生成最小生成树的每一步结果。
- 4.用Prim算法求下图的最小生成树, 若从顶点0出发，请将算法中的两个辅助数组的变化过程填入下表。
用普里姆(Prim)算法求出下图的最小生成树。
prim就是每次找和当前已知树距离最小的节点
具体：
（1）把1当作已知的，ans=0
（2）2节点离当前树最近，加入2，ans=16
（3）3离当前树最近，加入3，ans=16+5=21
（4）加入4，ans=21+6=27
（5）加入6（注意加入的权值为11），ans=27+11=38
（6）最后加入5，ans=38+13=51（那条边是18还是13）
（7）生成了最小生成树
最小生成树 普里姆算法和克鲁斯卡尔算法
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条边为止。
--以上传自hi.baidu/valyanprogramming/blog/item/1bc960e6095f9726b93820d9.html
1.Kruskal
//题目地址:acm.pku.edu/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;
}
代码来自网络
设某带权无向图如下图，画出用Prim算法，从顶点A开始生成最小生成树的每一步结果。
不会画，和你文字描述好了，你自己画出来
第一步连AE
第二步连EG
GC
GF
AD
BD
4.用Prim算法求下图的最小生成树, 若从顶点0出发，请将算法中的两个辅助数组的变化过程填入下表。
不好意思吖按照图弄那两个中间数组太久了。。。实现方法也有不同。我跟您说说我学的通用实现方法吧！
点集合：A，代表已经扩展到的点。
边集合B：代表待考虑的边，一开始为空。
一开始从任意点出发，如0.此时集合A中只有点0。将和A相邻的所有边加入到B中。
从B中选最短的一条边e。e的一个端点必不在A中，则将它加入A中。将不在A中的那个点的所有边加入B中，在B中删除边e
这样B中减少了一条边（先前的边中最短的）。在A中增加了一个新点，并且这个点的相关边加入了B中。而B中减少的这条边就是最小生成树的一条边。
这样一来，调用以上两个步骤N-1次（有N个点），则可以得到n-1条线段，就是其最小生成树。
如果不是很懂可以Q我，我会用通俗的语言解释的^^
QQ:328880142