在图采用邻接表存储时，求最小生成树的Prime算法的时间复杂度为?
A o(n^2) B o(n^3) C o(n) D o(n+e)
答案是o(n+e)。。。不理解..求过程
在图采用邻接表存储时，求最小生成树的Prime算法的时间复杂度为?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
分享- 邀请回答
-
4条回答 默认 最新
threenewbee 2015-01-25 11:24关注不对，这题应该选A
求顶点的入度的时间复杂度为O(e)*n=O(n*e)
遍历顶点的时间复杂度是O(n^2)
相加是O(n^2+n*e)=O(n^2)本回答被题主选为最佳回答 , 对您是否有帮助呢?评论 打赏解决 12无用 29举报 分享
- 2015-01-25 09:15回答 4 已采纳 不对，这题应该选A 求顶点的入度的时间复杂度为O(e)*n=O(n*e) 遍历顶点的时间复杂度是O(n^2) 相加是O(n^2+n*e)=O(n^2)
- 2019-01-06 00:54回答 1 已采纳 https://blog.csdn.net/zhousenshan/article/details/53140979
- 2021-08-27 21:56回答 1 已采纳 邻接表你可以理解为多个链表，每个链表的头是一个节点，而你添加一条边add（a,b,c）相当于给a增添一个出度b长度为c，而 next[a]中储存的是就是a所有的出度的地址，next存储的是下一个出度的
- 2015-12-09 21:24杨龙飞的博客的博客 1.prime算法思想:(只与顶点有关)prime算法求最小生成树时，和边数无关，只和顶点的数量有关，时间复杂度是O(n^2),所以呢，适合于求稠密网的最小生成树;将一个图的顶点分为两部分,一部分是最小生成树的集合，这里就记...
- 2021-05-28 18:08回答 1 已采纳 在邻接表中，边实际上就是顶点的一部分，你可以把它们都放到顶点的结构体中，也没问题。这个地方把它单独抽象出来是为了让整个数据结构更加清晰。
- 2021-10-24 23:17回答 2 已采纳 爆红的那句上面应该是缺了malloc
- 2022-08-19 19:31回答 2 已采纳 #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define
- 2018-01-30 12:38沫沫就沫沫好了的博客 以下是使用邻接表存储表示的，最小生成树prim算法的应用实例。 用于演示的图如下： #include #define MaxVertexNum 6 #define MAXNUM 65535 using namespace std; //抽象数据类型 typedef char vertextype;//顶点...
- 2021-06-20 21:06回答 2 已采纳 可以参考这篇文章，希望对你有帮助：邻接矩阵转换为邻接表；邻接表转换为邻接矩阵_Atlas！的博客-CSDN博客
- 2022-03-20 22:06回答 1 已采纳 n是图的顶点个数，e代表邻接表表示法边的个数。很容易认为n和指数没有关系，其实还真有关系，指数的个数就是顶点个数，查找每个顶点需要查找的边的个数的总和就是e，时间复杂度一分不差就是o(n+e).
- 2022-11-25 00:52回答 1 已采纳 DFS #include <vector> class MyGraph { protected: int vertexNum;//顶点数量 bool** matrix;/
- 2022-11-05 13:04算法给的安全感的博客 Prim算法 最小生成树
- 2021-07-06 18:55回答 1 已采纳 参考一下：https://blog.csdn.net/xueying_2017/article/details/78797784 如果对你有帮助，可以点击我这个回答右上方的【采纳】按钮，给我个采纳吗，
- 2015-11-13 20:43wwy1029258584的博客 Prime算法 分类： 算法总结2011-...普利姆算法求最小生成树时候，和边数无关，只和定点的数量相关，所以适合求稠密网的最小生成树，时间复杂度为O（n*n）。 算法过程： 1.将一个图的顶点分为两部分，一部
- 2023-12-15 21:05椿湫悠悠的博客 Kruskal算法是一种贪心算法，用于求解最小生成树问题。
- 没有解决我的问题, 去提问
悬赏问题
- ¥15 如何让子窗口鼠标滚动独立，不要传递消息给主窗口
- ¥15 如何能达到用ping0.cc检测成这样？如图
- ¥15 关于#DMA固件#的问题，请各位专家解答！
- ¥15 matlab生成的x1图不趋于稳定，之后的图像是稳定的水平线
- ¥15 请问华为OD岗位的内部职业发展通道都有哪些，以及各个级别晋升的要求
- ¥20 微信小程序 canvas 问题
- ¥15 系统 24h2 专业工作站版，浏览文件夹的图库，视频，图片之类的怎样删除？
- ¥15 怎么把512还原为520格式
- ¥15 MATLAB的动态模态分解出现错误，以CFX非定常模拟结果为快照
- ¥15 求高通平台Softsim调试经验