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

admin2018-07-17 74

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

若将该图看成无向图，用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://www.kaotiyun.com/show/jyRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

在下列我国建国之后的外交活动中，能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊

1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。

以下选项不属于希腊城邦的形成方式和途径的是()。

在辛亥革命爆发前，孙中山领导中国同盟会发动的武装起义中影响最大的是()。

巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。

下列城市：①南京②厦门③天津④杭州，按其在近代历史上开放为商埠的时间先后顺序排列应该是()

改革开放以来，乡镇企业的异军突起，其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径

解放军渡江战役中横渡长江的东西两个攻击点是()。

解放军渡江战役中横渡长江的东西两个攻击点是()。

某建设项目在市中心依法使用临时用地，并修建了临时建筑物，超过批准期限后仍未拆除。对此，下列哪一机关有权责令限期拆除?

1822年，英国人巴贝奇首先提出来整个计算过程自动化的概念，设计出了第一台通用自动时序控制机械式计算机，称为___________。

佝偻病初期的辅助检查错误的是

经接触疫水传播的传染病的流行特征

当归六黄汤药物组成中不含有

A、冠心苏合丸B、人参再造丸C、通心络胶囊D、九气拈痛丸E、血府逐瘀口服液患者，女，80岁，中风半年，症见口眼[*]斜，半身不遂，手足麻木，疼痛，拘挛，言语不清，证属气虚血瘀，风痰阻络，宜选用的中成药是

开工前复核基准点、基准线和高程时发现问题，应从()获取准确结果。

“后驱”是指发动机的动力通过传动轴传递给后轮，从而推动车辆前进的一种驱动形式。当后驱车在水平公路上匀速前进时，下列说法正确的是（）。

下列对法国的统一学校运动的阐述错误的是

Excel工作表D列保存了18位身份证号码信息，为了保护个人隐私，需将身份证信息的第3、4位和第9、10位用“*”表示，以D2单元格为例，最优的操作方法是()。