普林姆算法
❶ 利用普里姆算法求解最小生成树，写出步骤或画图表示过程。
<1,6>边长度未知，这里看成无穷大。
历次循环中，选择两端点分别在U，V中的边中长度最小者，
具体如下：
1. 将1加入U中，其余点加入V中。
2. 选择边<1,7>，将7加入U中，从V中除去该点。
3. 选择边<7,6>，将6加入U中，从V中除去该点。
4. 选择边<1,2>，将2加入U中，从V中除去该点。
5. 选择边<2,3>，将3加入U中，从V中除去该点。
6. 选择边<2,4>，将4加入U中，从V中除去该点。
7. 选择边<2,5>，将5加入U中，从V中除去该点。
结束。由上述六条边组成的树为求得的最小生成树。
❷ 利用Prim（普里姆）算法 构造最小生成树 程序
算法同样是解决最小生成树的问题。
其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。
与prim算法的不同：prim算法为单源不断寻找连接的最短边，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。
复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。
Prim算法用于求无向图的最小生成树
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)
Prim算法实现：
（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}
❸ 普里姆算法是什么
在计算机科学中，普里姆(也称为Jarník's)算法是一种贪婪算法，它为加权的无向图找到一个最小生成树 。
相关简介：
这意味着它找到边的一个子集，能够形成了一个包括所有顶点的树，其中在树中所有边的权重总和最小。该算法通过从任意起始顶点开始一次给树增加一个顶点来操作，在每个步骤中添加从树到另一个顶点的花费最小的可能的连接。
该算法由捷克数学家沃伊茨奇·贾尼克于1930年开发后，后来在1957年被计算机科学家罗伯特·普里姆，以及在1959年被艾兹赫尔·戴克斯特拉重新发现和重新出版。因此，它有时也被称为Jarník算法,普里姆-jarník算法。普里姆-迪克斯特拉算法或者DJP算法。
这个问题的其他众所周知的算法包括克鲁斯卡尔算法和 Borvka's算法。这些算法在一个可能的非连通图中找到最小生成森林；相比之下，普里姆算法最基本的形式只能在连通图中找到最小生成树。然而，为图中的每个连通分量单独运行普里姆算法，也可以用于找到最小生成森林。
就渐近时间复杂度而言，这三种算法对于稀疏图来说速度相同，但比其他更复杂的算法慢。然而，对于足够密集的图，普里姆算法可以在线性时间内运行，满足或改进其他算法的时间限制。
❹ 普林算法如果两条边权相同怎么办
普利姆算法（prim算法），每次选择最小边的时候，可能存在多条同样权值的边可选，此时任意选其一就可以。
参考资料：数据结构（C语言版 第二版）
❺ 普里姆算法
你要先明白prim算法的原理，明白原理后看下面的程序要点：
1.程序实现的时候将点分成两部分，加入集合的和没有加入集合的；
2.每次从没有加入集合中找点；
3.对所有没有加入到集合中的点中，找一个边权最小的；
4.将边权最小的点加入集合中，并且修改和加入点相连的没有加入的点的权，重复第2步，知道所有的点都加入到集合中；
❻ 普里姆算法的普里姆算法的实现
为了便于在两个顶点集U和V-U之间选择权最小的边，建立了两个辅助数组closest和lowcost，它们记录从U到V-U具有最小权值的边，对于某个j∈V-U，closest[j]存储该边依附的在U中的顶点编号，lowcost[j]存储该边的权值。
为了方便，假设图G采用邻接矩阵g存储，对应的Prim(g,v)算法如下：
void Prim(MatGraph g,int v) //输出求得的最小生树的所有边
{ int lowcost[MAXVEX]; //建立数组lowcost
int closest[MAXVEX]; //建立数组closest
int min,i,j,k;
for (i=0;i<g.n;i++) //给lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //构造n-1条边
{ min=INF; k=-1;
for (j=0;j<g.n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j];
k=j; //k为最近顶点的编号
}
printf( 边(%d,%d),权值为%d
,closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<g.n;j++) //修正数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{ lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
普里姆算法中有两重for循环，所以时间复杂度为O(n2)，其中n为图的顶点个数。由于与e无关，所以普里姆算法特别适合于稠密图求最小生成树。