2. 考研
  3. 下图所示是一带权有向图的邻接表。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求： 若将该图看成无向图，用Prim算法给出图G的一棵最小生成树的生成过程。

下图所示是一带权有向图的邻接表。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求： 若将该图看成无向图，用Prim算法给出图G的一棵最小生成树的生成过程。

admin2018-07-17  38
问题 下图所示是一带权有向图的邻接表。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：

若将该图看成无向图，用Prim算法给出图G的一棵最小生成树的生成过程。
选项
答案从V1点开始，第一趟寻找V1和点集{V2，V3，V4，V5，V6}之间的最小权值的边。(V5，V1)。 第二趟寻找点集{v1，V5}和点集{V2，V3，V4，V6)之间的最小权值的边。(V5，V6)。 第三趟寻找点集{V1，V5，V6}和点集{V2，V3，V4}之间的最小权值的边。(V1，V4)。 第四趟寻找点集{V1，V4，V5，V6}和点集{V2，V3}之间的最小权值的边。(V4，V2)。 第五趟寻找点集{V1，V2，V4，V5，V6}和点集{V3}之间的最小权值的边。(V2，V3)。 所以最小生成树的边集合为{(V5,V1)，(V5,V6)，(V1，V4)，(V4,V2)，(V2,V3)}。
解析
转载请注明原文地址:https://kaotiyun.com/show/jyRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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