2. 考研
  3. 使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。 对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。

使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。 对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。

admin2018-08-17  44
问题 使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。
对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。
选项
答案Prim算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为止。算法每一步在连接树集合S中顶点和其他顶点的边中，选择一条使得树的总权重增加最小的边加入集合S。当算法终止时，S就是最小生成树。 ①S中顶点为A，候选边为(A，D)、(A,B)、(A，E)，选择(A，D)加入S。 ②S中顶点为A、D，候选边为(A，B)、(A，E)、(D,E)、(C,D)，选择(D,E)，加入S。 ③S中顶点为A、D、E，候选边为(A，B)、(C，D)、(C,E)，选择(C,E)加入S。 ④S中顶点为A、D、E、C，候选边为(A，B)、(B，C)，选择(B，C)加入S。 ⑤S就是最小生成树。 依次选出的边为： (A，D)，(D，E)，(C，E)，(B，C)
解析
转载请注明原文地址:https://kaotiyun.com/show/FSRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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