Prim算法和Kruscal算法都是无向连通网最小生成树算法，Prim算法从一个顶点开始，每次从剩余顶点中加入一个顶点，该顶点与当前生成树中顶点连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小边开始，每次从不在当前生成树顶点中选择权重最小边加入，直到得到一颗最小生成树，这两个算法都采用了（请作答此空）设计策略，且（ ）。
- A.分治
- B.贪心
- C.动态规划
- D.回溯
正确答案及解析
正确答案
B
解析
Prim算法从扩展顶点开始，每次总是"贪心"选择与当前顶点集合中距离最短顶点，而Kruscal 算法从扩展边开始，每次总是"贪心"选择剩余边中最小权重边，因此两个算法都是基于贪心策略进行。
Prim 算法时间复杂度为O(n2)，其中n 为图顶点数，该算法计算时间与图中边数无关，因此该算法适合于求边稠密图最小生成树；Kruscal 算法时间复杂度为O(mlgm) ，其中m 为图边数，该算法计算时间与图中顶点数无关，因此该算法适合于求边稀疏图最小生成树。当图稠密时，用 Prim 算法效率更高。但若事先没有关于图拓扑特征信息时，无法判断两者优劣。由于一个图最小生成树可能有多棵， 因此不能保证用这两种算法得到是同一棵最小生成树。
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案