给定一个无向连通带权图G=(V,E),下述关于prim算法说法正确的是()。
A: prim算法先选出一个顶点加入到集合S,把图的顶点分成两个集合,一个S,一个V-S
B: prim算法总是选择连接S和V-S的边中权最小的加入到最小生成树中。
C: prim算法停止的条件是S=V
D: prim算法的时间复杂度O(n2),n为图的顶点个数。
E: prim算法的阶和图的顶点数有关,也和图的边数也有关。
F: prim算法的时间复杂度O(n3),n为图的顶点个数。
A: prim算法先选出一个顶点加入到集合S,把图的顶点分成两个集合,一个S,一个V-S
B: prim算法总是选择连接S和V-S的边中权最小的加入到最小生成树中。
C: prim算法停止的条件是S=V
D: prim算法的时间复杂度O(n2),n为图的顶点个数。
E: prim算法的阶和图的顶点数有关,也和图的边数也有关。
F: prim算法的时间复杂度O(n3),n为图的顶点个数。
举一反三
- 【单选题】给定一个无向连通带权图G=(V,E),下述关于prim算法说法不正确的是( )。 A: prim算法先选出一个顶点加入到集合S,把图的顶点分成两个集合,一个S,一个V-S B: prim算法总是选择连接S和V-S的边中权最小的加入到最小生成树中。 C: prim算法停止的条件是S=V D: prim算法的时间复杂度O(n3),n为图的顶点个数。
- 给定一个无向连通带权图G=(V,E),n个顶点,e条边,prim算法的时间复杂度为() A: O(n2) B: O(n3) C: O(eloge) D: O(nlogn)
- 案例分析题对于n个顶点e条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为（），利用Kruskal算法生成最小生成树的时间复杂度为（）。 对于n个顶点e条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为（） A: O（（n+1）2） B: O（n2） C: O（n2-1） D: （n2+1）
- 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（ ）
- 对于n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（ ）。 A: O(n*n) B: O(n) C: O(e) D: O(nlogn)