首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
G=(V,E)是一个带有权的连通图,如图所示。 G如图所示,请找出G的所有最小生成树。
G=(V,E)是一个带有权的连通图,如图所示。 G如图所示,请找出G的所有最小生成树。
admin
2019-08-15
22
问题
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://kaotiyun.com/show/edCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
“葡萄牙人在非洲海岸、印度和整个远东寻找的是黄金,黄金一词是驱使西班牙人横渡大西洋到美洲去的咒语;黄金是白人刚踏上一个新发现的海岸时所要的第一件东西。”欧洲人对黄金的贪婪追求从本质上反映了()
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
设有m个连续单元供一个栈与队列使用,且栈与队列的实际占用单元数事先不知道,但是要求在任何时刻它们占用的单元数量不超过m,试写出上述栈与队列的插入算法。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
进程从运行状态转换为就绪状态的可能原因是()。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijkstra算法求出从结点A到所有其他结点的最短路由。
以下关于CPU的叙述中,错误的是()。
一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。
随机试题
市场营销管理的实质是()。
男,36岁,上腹痛,腹泻半年,伴纳差、乏力、消瘦。体温37.5℃,巩膜黄染,上腹压痛,肝脾未及,移动性浊音阳性确诊最重要的检查是
“沙利度胺治疗妊娠呕吐导致无肢胎儿”属于
银屑病鳞屑临床表现是
路面回弹弯沉的温度修正可以根据查图法进行,修正后的路面回弹弯沉公式为()。
土地的使用条件包括()。
以下不属于总监理工程师职责的是( )。
强调引导儿童从原有的知识经验中习得新的知识经验的理论学派是()。
垄断统治下竞争的特点有()。
Abreakthrough(突破)intheprovisionofenergyfromthesunfortheEuropeanEconomicCommunity(EEC)couldbebroughtforwardb
最新回复
(
0
)