首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
G=(V,E)是一个带有权的连通图,如图所示。 G如图所示,请找出G的所有最小生成树。
G=(V,E)是一个带有权的连通图,如图所示。 G如图所示,请找出G的所有最小生成树。
admin
2019-08-15
57
问题
G=(V,E)是一个带有权的连通图,如图所示。
G如图所示,请找出G的所有最小生成树。
选项
答案
最小生成树有两棵。下面给出顶点集合和边集合,编以三元组(V
i
,V
j
,W)形式,其中W代表权值。 V(G)={1,2,3,4,5} E1(G)={(4,5,2),(2,5,4),(2,3,5),(1,2,7)}; E2(G)={(4,5,2),(2,4,4),(2,3,5),(1,2,7)} 提示:此题考查的知识点是最小生成树的定义。该题说明图的最小生成树不唯一,但权值和唯一,出现两个或两个以上的情况是因为有权值相同的边。牢记Prim(选图的顶点)、Kruskal(选图的边,边上权值排序)两种算法的区别及算法步骤。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/edCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1956年11月,中共八届二中全会决定开展的全党整风运动要反对的错误倾向是()。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
某DRAM芯片内部存储元排列成1024.×1024的矩阵,且已知其存取周期为0.1μs,最大刷新间隔为2ms。当采用异步刷新方式时,死时间()。
下列关于最小生成树的叙述中,正确的是I.最小生成树的代价唯一Ⅱ.权值最小的边一定会出现在所有的最小生成树中Ⅲ.使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同Ⅳ.使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
随机试题
A.恶性黑色素瘤B.皮肤基底细胞癌C.皮肤鳞状细胞癌D.神经纤维瘤E.瘢痕癌颞部皮肤表面出现向外及向四周隆起的小结节,其中心部位短时间内出现破溃坏死,四周向外翻出,呈菜花状,首先考虑诊断为
某商场给某商贸公司签发了授权委托书,委托其代买100台春兰空调。商贸公司见今年夏天天气炎热,空调销路好,海尔空调更是畅销,于是以商场的名义自主决定向某空调销售公司购买了100台春兰空调,又购买了100台海尔空调。空调销售公司虽然查看了商贸公司的授权委托书,
县级以上地方人民政府负责管理测绘工作的行政部门负责本行政区域测绘工作的()。
背景资料:某施工单位承建了某高速公路路面工程,其主线一般路段及收费广场路面结构设计方案见下表。备注:1.沥青路面的上、中面层均采用改性沥青。2.沥青路面面层之间应洒布乳化沥青作为C,在水泥稳定碎石基层上应喷洒液体石油沥青作为D,之后应设置
下列各项关于无形资产会计处理的表述中,正确的是()。
关于现金流量套期,下列会计处理表述中,错误的是()。
()对于孩子相当于()对于员工
中国北派山水画雄伟风格的代表人物有()。
Theword"freedom"formanyblackAmericansisinextricablylinkedwiththeword"slavery."Whileithas148years【M1】______si
WhichofthefollowingsentencesisINCORRECT?
最新回复
(
0
)