prim算法的时间复杂度怎么样

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

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

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

扩展资料：

算法描述：

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来描述所得到的最小生成树。

设在生成G的过程中第一次产生的不在T中的边是e，而在G中去掉e得到的两个连通分支记为V1和V2，那么e连接了V1和V2

把e加入T之后会出现环，在这个环里面V1的顶点和V2的顶点至少还被另一条边f连接（否则T本身就不连通了），由Prim算法的贪心策略可知e比f权重低，那么在T里面把f换成e可得一个总权重更小的生成树，与T的最小性矛盾。

你要先明白prim算法的原理，明白原理后看下面的程序要点：

1程序实现的时候将点分成两部分，加入集合的和没有加入集合的；

2每次从没有加入集合中找点；

3对所有没有加入到集合中的点中，找一个边权最小的；

4将边权最小的点加入集合中，并且修改和加入点相连的没有加入的点的权，重复第2步，知道所有的点都加入到集合中；

n个点求最小生成树，需要n-1条边。

我们希望取最小的n-1条边。如（n=8）

1,2,3,4,7,8,10,11,13,15

我们取前7条1,2,3,4,7,8,10，而3,4,8这三条边构成环。我们去掉其中的一条边，增加另一条边，使增加的长度最小，所以我们去除环中最长的边8，增加剩余的边中最短的边11，如此循环，得到最小生成树。

如果你承认以上得到的是全局最优解，请接着往下看

而prim的原理与上面的过程类似，当一直从最小的边开始取边，取到8的时候构成环，放弃8，继续取边。直到取到n-1条边。

不能。Prim是求最小生成树的算法，不能等效为最短路径。如图(参考自《王道考研系列——数据结构》)

但是Dijkstra算法，和Floyd算法可以求最短路径。

以上就是关于prim算法的时间复杂度怎么样全部的内容，包括:prim算法的时间复杂度怎么样、存在负权重边时prim算法有效吗、普里姆算法等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！