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

admin2018-07-17 32

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

若将该图看成无向图，用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://jikaoti.com/ti/WlfjFFFM

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

结束雅各宾派专政的历史事件是()。

武昌起义()。①由同盟会直接领导②原计划被偶然因素打乱③其成功有深刻的社会原因④迅速的胜利潜伏着失败的危机

外国侵略者火烧圆明园事件是发生在()中。

宋在金的压力下，不得不杀了降宋的原辽将()，以其首献于金朝，这对于原辽降于宋朝的将领产生了极大的消极影响

党锢事件发生后，清议的浪潮更为高涨，度辽将军()没有被当做名士列入党锢，甚至自陈与党人的关系，请求连坐。

关于希腊早期宗教的叙述不正确的是()。

下列哪个文件标志着“文化大革命”的发起?()

全国高校院系调整的具体时间是()。

将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是()，最多需要比较的次数是()。

橄榄桥小脑萎缩蛛网膜下腔出血

最易发生抗原变异的病毒是()

慢性肾衰竭病人尿量的变化特点是

甲乙为夫妻，父母双亡，膝下无子，甲有一弟。甲乙因同坐一架飞机遇事而亡。经查，甲乙有共同财产20万元，对该20万元()。

在风险性上，相对来说()要大一些。

按照银监会对个人理财业务的定义，商业银行为销售储蓄存款产品、信贷产品等进行的产品介绍和宣传不属于理财顾问服务。()

患者，男性，37岁。发热、咳嗽、胸痛1个月，门诊就诊。如果你是首诊医生，问诊应包括哪些内容?

EnricoMingardispentagoodpartofthemorningwithmeexplaininghisideasonhewtoimprovethewater-busserviceinVenice.