首页 > 试题广场 >

对于含有n个顶点e条边的连通图，利用prim算法求最小生成数

[单选题]
对于含有n个顶点e条边的连通图，利用prim算法求最小生成数的时间复杂度为（） 
  • O(n²)
  • O(e²)
  • O(nlog₂n)
  • O(elog₂e)
添加回答
Rnanprince头像 Rnanprince
首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。（加入之后如果产生回路了就要跳过这条边，选择下一个结点。）当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树。
首先，初始化部分所需时间为Ο(|V|+|E|)。其次，在|V|-1次循环过程中，一方面要遍历各个顶点的邻接边，一共需要Ο(|E|)的时间；另一方面在每次循环中查找轻边需要对所有顶点遍历一遍，每次循环需时Ο(|V|)。因此算法的时间复杂度T(n) =Ο(|V|+|E|) +Ο(|E|) + (|V|-1)Ο(|V|) =Ο(|V|^2+|E|) =Ο(|V|^2)。
边数较多可以用Prim，因为它是每次加一个顶点，对边数多的适用。
综上，选择A
编辑于 2018-05-17 17:38:06 回复(0)
天尊墨宇头像 天尊墨宇
选A
首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。（加入之后如果产生回路了就要跳过这条边，选择下一个结点。）当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树。
首先，初始化部分所需时间为Ο(|V|+|E|)。其次，在|V|-1次循环过程中，一方面要遍历各个顶点的邻接边，一共需要Ο(|E|)的时间；另一方面在每次循环中查找轻边需要对所有顶点遍历一遍，每次循环需时Ο(|V|)。因此算法的时间复杂度T(n) =Ο(|V|+|E|) +Ο(|E|) + (|V|-1)Ο(|V|) =Ο(|V|^2+|E|) =Ο(|V|^2)。
边数较多可以用Prim，因为它是每次加一个顶点，对边数多的适用。
综上，选择A
发表于 2020-07-10 17:51:06 回复(0)
提交观点

问题信息

图
上传者：喵大人喵喵喵
难度：
2条回答 4530浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号