首页 > 试题广场 > 在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度
[单选题]
在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为()
  • O(n)
  • O(n+e)
  • O(n2)
  • O(n3)
如果大家相信我的话,我可以打包票,这题是错的!
如果用邻接矩阵存储的话,Prim算法时间复杂度是O(n^2)  克鲁斯卡尔(Kruskal)算法  时间复杂度O(eloge)  这个没有问题。
但是,用邻接表存储的话,Prim算法时间复杂度是O(n + e)???
首先,考虑一下隔壁算法---克鲁斯卡尔(Kruskal)算法的感受:你负责稠密图,我负责稀疏图,我们井水不犯河水,各自占领最小生成树的半壁江山。好了,现在你用邻接矩阵存储,时间复杂度降到O(n+e)直接跟遍历算法一个量级,还能不能好好做朋友了???以后,这般程序猿还会使用我这个算法吗?你这是要我吃土啊!我不服!!!

大家想想也应该知道,的确不可能降这么多的,正确的时间复杂度,应该为   邻接表:O(elog 2 v)
维基百科给出的答案是这个:


至于O(n+e),我敢说必然错了!求打脸
发表于 2017-07-09 14:18:02 回复(2)
记住了 Prim算法的时间复杂度     邻接表存储时,是 O(n+e)
                                                  图的时候 是O(n^2)
发表于 2016-03-06 21:15:31 回复(4)
答案:选C
邻接表是O(n+e),邻接矩阵存储是O(n2
发表于 2015-01-13 00:40:26 回复(3)
答案是错的,B对应的是图的遍历问题时的时间复杂度,而题目问的生成最小生成树,应选C
发表于 2015-08-21 10:39:30 回复(1)
 










以上是我封装的用邻接表表示的图以及Prim算法的实现。下面简单分析一下:
Prim实现的核心的部分请看for循环。
Prim算法的思路是每次从备选点中选取一个连接代价最小的点加入最小生成树,初始状态最小生成树只有一个点,若该图有n个点,则还需要选择n-1次。这是外层循环(如下)的含义。
for (int i = 0; i < g.vexnum - 1; i++) {//一次选取一个点并入U,除初始点,还需并入g的结点数 - 1次
但是要怎么才能知道每次该选哪一个点呢?这就是内层循环的工作,去遍历不在集合U中的点(即不在最小生成树中的点),更新该点与集合U相连的最小代价lowcost,若该点与U不相连,则连接代价为INF。代码如下:
for (int j = 0; j < g.vexnum; j++) {
            if (U[j] == true)//j已经在U中,直接跳过
                continue;
            ArcNode* p = g.vertices[j].firstArc;
            while (p) {
                if (U[p->adjvex] == true) {//连接的点在U中
                    if (p->weight <= lowcost[j]) {//且代价小
                        //更新adjvex和lowcost
                        adjvex[j] = p->adjvex;
                        lowcost[j] = p->weight;
                        if (p->weight < mincost) {
                            mincost = p->weight;
                            mincostIndex = j;
                        }
                    }
                }
                p = p->nextarc;
            }
        }
每次选点加入最小生成树之前都需要对lowcost重新进行计算,计算一次lowcost的时间复杂度为O(n),那么Prim的时间复杂度粗略计算为O(n*n)。故答案选C

那么邻接表相比邻接矩阵实现Prim算法效率提高在了哪里呢?在计算某点的lowcost的时候,如果用邻接矩阵,需要遍历矩阵的一行也就是n次来找到跟当前结点连接的点;如果用邻接表,就可以将遍历次数从n下降到与该点相连的边数e。

能力有限,我的实现方法是用的最笨的,所以时间复杂度不是e*log(n),若有错误的地方还请大家指正。


编辑于 2019-06-30 11:33:19 回复(1)
普利姆算法,采用邻接表存储,复杂度为 O(n+e);采用邻接矩阵,图的时候是O(n2)。
编辑于 2017-01-07 15:15:54 回复(0)

Prim 首先以一个结点作为最小生成树的初始结点,然后以迭代的方式找出最小生成树中各结点权重最小的边,并加到最小生成树中。(加入之后如果产生回路了就要跳过这条边,选择下一个结点。)当所有的结点都加入到最小生成树中后,就找出了这个连通图的最小生成树。
首先,初始化部分所需时间为Ο(|V|+|E|)。其次,在|V|-1次循环过程中,一方面要遍历各个顶点的邻接边,一共需要Ο(|E|)的时间;另一方面在每次循环中查找轻边需要对所有顶点遍历一遍,每次循环需时Ο(|V|)。因此算法的时间复杂度T(n) =Ο(|V|+|E|) +Ο(|E|) + (|V|-1)Ο(|V|) =Ο(|V|^2+|E|) =Ο(|V|^2)。
边数较多可以用Prim,因为它是每次加一个顶点,对边数多的适用。
-------------------------------------------------------------
Kruskal算法在找最小生成树结点之前,需要对权重从小到大进行排序。将排序好的权重边依次加入到最小生成树中,(如果加入时产生回路就跳过这条边,加入下一条边)。当所有的结点都加入到最小生成树中后,就找到了这个连通图的最小生成树。
算法总的时间取决于排序步,即Ο(|E| log |E|)。
边数较少可以用Kruskal,因为Kruskal算法每次查找最短的边。

即n^2;eloge
发表于 2018-05-17 17:44:08 回复(0)
B肯定是错误的,但是c也不对,采用邻接表存储时能起到降低时间复杂度的作用,但也是像百科上说的应该为o(elogv)。 要是能降低到n+e,估计普里姆听了是要骂娘的。。。
发表于 2017-08-05 16:27:04 回复(0)
邻接表的时候为B 邻接矩阵为C
发表于 2015-11-23 21:31:30 回复(0)
b
发表于 2019-05-02 11:13:07 回复(0)
邻接表+二叉最小堆,ElogV
发表于 2019-01-01 19:39:53 回复(0)
普里姆算法是选点进集合,而克鲁斯卡尔算法选的是边。
发表于 2018-10-24 10:16:00 回复(0)
prim算法的时间复杂度V^2不依赖与E,所以才适合于求边稠密图
发表于 2017-10-29 17:44:05 回复(0)
最小边、权的数据结构 时间复杂度(总计)
邻接矩阵、搜索 O(V^2)
二叉堆(后文伪代码中使用的数据结构)、邻接表 O((V + E) log(V)) = O(E log(V))
斐波那契堆邻接表 O(E + V log(V))

发表于 2017-07-12 00:16:02 回复(0)
邻接表:O(n+e)
邻接矩阵:O(n^2)
发表于 2017-06-26 11:19:51 回复(0)
Prim算法的时间复杂度:1. 邻接表存储时,是 O(n+e) 2. 图的时候 是O(n^2)
发表于 2017-06-14 13:56:02 回复(0)
这个题选择B,如果是邻接矩阵的话选择C

发表于 2017-01-01 17:14:43 回复(0)
这题题目是不是中途改过了
发表于 2016-12-26 20:18:31 回复(0)
这题答案有问题,参考wiki百科:https://zh.wikipedia.org/wiki/%E6%99%AE%E6%9E%97%E5%A7%86%E7%AE%97%E6%B3%95
邻接表存储时时间复杂度为: O((V + E) log(V)) = O(E log(V)),其中V代表定点,E代表边
发表于 2016-09-07 09:48:24 回复(0)
觉得选c,思想是每次把临界表中n条边遍历一遍,找出最小边,下一次再在n-1条边中找最小边,重复这过程,若构成环路,则丢掉新加进来的边,找次小边。。。。直到所有点全部可达既可以。故:n+(n-1)+...  即O(n 2 )
发表于 2015-10-15 13:43:43 回复(2)