在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( ).

admin2014-10-20 32

问题在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( ).

选项 A、O(n)
B、O(n+e)
C、O(n2)
D、O(n3)

答案B

解析设N={V，{E})是连通网，TE是最小生成树中边的集合，初始为空。定义一个仅含一个顶点的集合U={u0}，u0∈V(u0可从顶点集合V中任意选取)，则将N中的所有顶点分成了两个集合：U，V—U。重复执行以下操作：在所有的u∈u，v∈V决定的边(u，v)∈{E}中寻找一条代价最小的边(u0，v0)，将该边并入TE集合，同时v0并入U，直到U=V为止。以上操作，通俗地讲，实际上是从两大阵营(两个图的顶点的集合)中寻找一条最短的路。Prim算法中，最小代价生成树的顶点和边都是逐步生成的，开始的时候顶点集合中有一个顶点，边的集合为空。

转载请注明原文地址:https://kaotiyun.com/show/MgvR777K

本试题收录于：计算机科学与技术题库普高专升本分类

计算机科学与技术

普高专升本

相关试题推荐

随机试题

最新回复(0)

在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( ).

计算机科学与技术

普高专升本

神经细胞在接受一次阈上刺激后，兴奋性的周期变化是()。

开颅术后并发血肿的观察内容不包括()。

按系统与环境的关系，系统分为()。

内分泌系统的反馈调节是指下丘脑—垂体—靶腺之间的相互调节。()

图示简支梁承受一对大小相等，方向相反的力偶，其数值为M，四种挠曲线中正确的是()。

关于图所示结构，下列结果错误的是()

自身免疫性疾病的基本特征是()

A参与DNA合成的原料B参与RNA合成的原料C参与辅酶NAD+的组成D参与供给能量E参与细胞信息传递cAMP()

文件系统的主要任务?

微型计算机采用总线结构，总线通常由数据总线、传输总线和通信总线组成。()

在Word2003的编辑状态下，当前编辑的文档是C盘中的d1．doc文档，要将该文档拷贝到U盘，应当使用__________。()

下列关于医疗机构擅自从事精神障碍诊断、治疗的法律责任的描述，不正确的是

贸易术语在国际贸易中的主要作用是()。

下列关于公司收购方式的陈述，正确的是()。

个性化分期还款协议的最长期限不得超过()年。

当事人拒绝履行已经发生法律效力的民事判决时，经另一方当事人申请，法院可以采取的强制执行措施有()。

下列对于《聊斋志异》的描述，不正确的是()。

Threecommonwaysofrememberingare:repetition,association,andexaggeration.Repetitionisthekeytolongtermmemory.【

Mr,andMrs.RajahHassimweregoingtoeatout.Mr.Hassimtelephonedinthemorningandreserved(预定)atableinSpringRestau