数据结构 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（ ），利用K
数据结构对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。求详细解答过程...
数据结构
对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（ ），利用Kruskal算法求最小生成树的时间复杂度为（ ）。
求详细解答过程 展开
对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（ ），利用Kruskal算法求最小生成树的时间复杂度为（ ）。
求详细解答过程 展开
1个回答
展开全部
O(n^2), O(elog2e)
求这两个结果的过程任何一本比较全面的数据结构教科书上都有的
求这两个结果的过程任何一本比较全面的数据结构教科书上都有的
追问
可以跟我讲一下吗？我的书没有
追答
Prim算法使用邻接矩阵来存储，一共n-1步，每步需要找出当前最小的邻接无环最小边，这个是比较n次
Kruskal 算法存储结构用邻接表，算法一般用堆+并查集完成，其中最大的时间是边长排序时间O(elog2e)
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
