首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。 对下列图G,从顶点A开始求G的MST,依次给出按算法选出的边。
使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。 对下列图G,从顶点A开始求G的MST,依次给出按算法选出的边。
admin
2018-08-17
23
问题
使用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
学硕统考专业
相关试题推荐
罗马共和国早期平民反对贵族斗争过程中,废除债务奴隶制的是()。
下列有关《布列斯特和约》的说法中,错误的一项是()。
根据材料,结合有关知识,回答问题:埃及的河流空了,人(可以)徒步涉过。人们找不到能行船的水。河床变成了沙滩。沙滩上没有水,河床上也没有水……一切好东西都不见了,这个地方枯竭了……土地缩小了,(但是)它的行政人员却很多。土地荒凉不毛;(但)税却很重,只有
提出行星绕太阳运行的轨道是椭圆形的天文学家是()。
“二战”后,联合国的成立反映了世界人民和平的愿望,下列叙述正确的是()。
下列有关西欧封建社会的表述,错误的一项是()。
西周的官僚制度已经相当完备,官僚机构庞杂,职官名目繁多。周王室的官僚机构分为两大系统,分别是()。
1984年,《中共中央关于经济体制改革的决定》中强调,商品经济的充分发展是社会经济发展不可逾越的阶段,市场调节的辅助性作用不可缺少,并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()
印度列国时代出现了16个国家,其中大部分是王国,只有少数的共和国。下列属于共和国的是()。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
随机试题
[2015]甲集团公司是ABC会计师事务所的常年审计客户,主要从事化妆品的生产、批发和零售。A注册会计师负责审计甲集团公司2014年度财务报表,确定集团财务报表整体的重要性为600万元。资料一:A注册会计师在审计工作底稿中记录了审计计划
下列关于X(γ)线全身照射剂量要求描述错误的是
A.千金止带丸B.妇科千金片C.盆炎净颗粒D.抗妇炎胶囊E.花红片症见带下黄稠,月经不调时应选用
各资产收益的相关性()影响组合的预期收益,()影响组合的风险。
某商场系增值税一般纳税人,适用增值税税率为17%。20×2年春节期间为进行促销,该商场规定购物每满200元积10分(每1积分的公允价值为1元),不足200元部分不积分,积分可在1年内使用。某顾客购买了售价为5850元(含增值税额850元)、成本为4000元
杨某在上海某企业工作时,发现很多在厂里工作的同事打算利用出门在外的机会再生育一个孩子,就说服同事张某私刻了××街道办事处的印章,为在上海的老乡孙某办理了一份计生证明,并收取300元费用。第二天,此事就被举报到上海市的有关计生管理部门,该计生管理部门可以:(
“江山易改,本性难移”是指个性的()。
简述人身权的概念和分类。
栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是______。
Thewoodwassorottenthat,whenwepulled,it______intofragments.
最新回复
(
0
)