2. 专升本
  3. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( ).

在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( ).

admin2014-10-20  84
问题 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为(    ).
选项 A、O(n)
B、O(n+e)
C、O(n2)
D、O(n3)
答案B
解析 设N={V，{E})是连通网，TE是最小生成树中边的集合，初始为空。定义一个仅含一个顶点的集合U={u0}，u0∈V(u0可从顶点集合V中任意选取)，则将N中的所有顶点分成了两个集合：U，V—U。重复执行以下操作：在所有的u∈u，v∈V决定的边(u，v)∈{E}中寻找一条代价最小的边(u0，v0)，将该边并入TE集合，同时v0并入U，直到U=V为止。以上操作，通俗地讲，实际上是从两大阵营(两个图的顶点的集合)中寻找一条最短的路。Prim算法中，最小代价生成树的顶点和边都是逐步生成的，开始的时候顶点集合中有一个顶点，边的集合为空。
转载请注明原文地址:https://www.kaotiyun.com/show/MgvR777K
本试题收录于： 计算机科学与技术题库普高专升本分类
0

计算机科学与技术

普高专升本

相关试题推荐
随机试题
最新回复(0)