普里木算法

⑴ 普里姆算法

可以这么理解：因为最小生成树是包含所有顶点的所以开始lowcost先储存到第一个点的所有值，然后执行下面算法，找到最小值并记录是第几个点，比如说这个点是3，这样有了一条1-3得道路已经确定，现在从3出发找从3出发到其他顶点的路径，如果这个从3出发到达的路径长度比从1出发的短，则更新lowcost，这样使得lowcost保存一直到达该顶点的最短路径。比如1-4是5，3-4是4，则lowcost从原来的5被改为4。

⑵ 关于prim算法的时间复杂度

Prim算法的时间复杂度与网中的边数无关，适合于稠密图。

通过邻接矩阵图表示的简易实现中，找到所有最小权边共需O（V）的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为O(ElogV)，其中E为连通图的边数，V为顶点数。

如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(E+VlogV)，这在连通图足够密集时（当E满足Ω（VlogV）条件时），可较显着地提高运行速度。

(2)普里木算法扩展阅读：

算法描述：

1、输入：一个加权连通图，其中顶点集合为V，边集合为E；

2、初始化：Vnew= {x}，其中x为集合V中的任一节点（起始点），Enew= {},为空；

3、重复下列操作，直到Vnew= V：

在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

将v加入集合Vnew中，将<u, v>边加入集合Enew中；

4、输出：使用集合Vnew和Enew来描述所得到的最小生成树。

⑶ 最小生成树 普里姆算法有问

普里姆算法构造最小生成树算法的思想是：选择一个结点，然后从这个结点开始，选择权值最小的边，用一条边连接，然后再以前面的那个结点开始，和你连接的那个结点作为根节点，再选择权值最小的边进行连接。
对权值给出解释：以上图为例，权值就是你第一个图那几条边（弧）上，所标的数字。
对楼主所提出的问题：并不是连接那圆圈中最小的圆圈，如果没错的话，那圆圈中的数字表示的是V1---V6六个顶点，并不是代表数字，以3和6为顶点，找权值最小边，显然6——4为最小，即权值为2，顶点364相连接的时候各以364为顶点寻找最小边，应该先从6连接到2，那么现在加入顶点的为3642顶点，现在以3642为顶点寻找最小边，应该从2连接到1，现在被连接的有63421，在以63421为顶点寻找最小边
出现了问题：如果以5为权值的话，无论从2连接到4还是从3连接到4都出现了环，当然我们知道数中是不能出现环的，所以寻找次小的，剩余5与13之间权值最小为13.所以将1连接5，即得到最小生成树。
楼主可以按照我说的在纸上画一下试试
从6连接到3因为有前提条件：从顶点V3开始用普里姆方法求其最小生成数，可见是从顶点3连接到6，而不是从6连接到3
希望可以解决楼主的疑惑，谢谢！

⑷ 什么是普利姆算法

Prim算法：是图的最小生成树的一种构造算法。

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

如果看不懂还可以找一本数据结构的书看，这个算法挺简单的。

btw：其实你有空问，应该有空网络啊~网络就有了。懒得写，我还是直接从网络过来的~

⑸ 普里姆算法是什么

在计算机科学中，普里姆(也称为Jarník's)算法是一种贪婪算法，它为加权的无向图找到一个最小生成树 。

相关简介：

这意味着它找到边的一个子集，能够形成了一个包括所有顶点的树，其中在树中所有边的权重总和最小。该算法通过从任意起始顶点开始一次给树增加一个顶点来操作，在每个步骤中添加从树到另一个顶点的花费最小的可能的连接。

该算法由捷克数学家沃伊茨奇·贾尼克于1930年开发后，后来在1957年被计算机科学家罗伯特·普里姆，以及在1959年被艾兹赫尔·戴克斯特拉重新发现和重新出版。因此，它有时也被称为Jarník算法,普里姆-jarník算法。普里姆-迪克斯特拉算法或者DJP算法。

这个问题的其他众所周知的算法包括克鲁斯卡尔算法和 Borvka's算法。这些算法在一个可能的非连通图中找到最小生成森林；相比之下，普里姆算法最基本的形式只能在连通图中找到最小生成树。然而，为图中的每个连通分量单独运行普里姆算法，也可以用于找到最小生成森林。

就渐近时间复杂度而言，这三种算法对于稀疏图来说速度相同，但比其他更复杂的算法慢。然而，对于足够密集的图，普里姆算法可以在线性时间内运行，满足或改进其他算法的时间限制。

⑹ 普里姆算法的普里姆算法的实现

为了便于在两个顶点集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无关，所以普里姆算法特别适合于稠密图求最小生成树。

⑺ 利用普里姆算法求解最小生成树，写出步骤或画图表示过程。

<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算法是什么

prim算法是图论中的一种算法。

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。

简介

最小生成树是数据结构中图的一种重要应用，它的要求是从一个带权无向完全图中选择n－1条边并使这个图仍然连通（也即得到了一棵生成树）,同时还要考虑使树的权最小。

为了得到最小生成树，人们设计了很多算法，最着名的有prim算法和kruskal算法。教材中介绍了prim算法，但是讲得不够详细，理解起来比较困难，为了帮助大家更好的理解这一算法，本文对书中的内容作了进一步的细化，希望能对大家有所帮助。

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

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

⑽ 普里姆算法的相关概念

1）生成树一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的，是连通图的极小连通子图，包含图中的所有顶点，有且仅有n-1条边。非连通图的生成树则组成一个生成森林；若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。
2）和树的遍历相似，若从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历，(Traversing Graph)。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。对每种搜索顺序，访问各顶点的顺序也不是唯一的。
3）在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G′称做图G的生成树。一个图可以有多个生成树，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边也就不同。
在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。常见的求最小生成树的方法有两种：克鲁斯卡尔(Kruskal)算法和普里姆（Prim）算法。