首页 > 试题广场 >

一个有n个结点的连通图的生成树是原图的最小连通子图，且包含原

[单选题]
一个有n个结点的连通图的生成树是原图的最小连通子图，且包含原图中所有n个结点，并且有保持图联通的最少的边。最大生成树就是权和最大生成树，现在给出一个无向带权图的邻接矩阵，权为0表示没有边。
{
{0，4，5，0，3}，
{4，0，4，2，3}，
{5，4，0，2，0}，
{0，2，2，0，1}，
{3，3，0，1，0}
}
求这个图的最大生成树的权和。 
  • 11
  • 12
  • 13
  • 14
  • 15
添加回答
推荐
行云流水头像 行云流水
D 利用kruskal，不同的是，这次我们按照从大到小的顺序，从图中选择边，同时保证选择该边不会与之前选过的边组成一个回路。最终选择5 4 3 2 四条边 
编辑于 2015-02-06 15:05:38 回复(1)
恶寒轻轻头像 恶寒轻轻
普里姆算法和克里斯卡尔算法都可以的
发表于 2021-11-25 15:35:51 回复(0)
黎曼流形的铺头像 黎曼流形的铺
克鲁斯卡尔
发表于 2017-02-10 00:23:54 回复(0)
披萨大叔头像 披萨大叔
发表于 2016-09-05 11:42:10 回复(2)
sunlight_run头像 sunlight_run

A B C D E
A 0 4 5 0
3
B 4 0 4 2 3
C 5 4 0 2 0
D 0 2 2 0 1
E 3 3 0 1 0

选择最大的边加入，但是不能形成回路，图中表黑的就是被选出的，DE边是不能选的，否则就形成闭路。总共5+4+3+2=14
发表于 2017-06-28 19:13:53 回复(0)
小胡同学ccnu头像 小胡同学ccnu
D
kruskal算法。我们平时是求最小生成树，也可以同理求出最大生成树。先根据给出的矩阵画出图，5个顶点可以用A、B、C、D、E表示。然后每一次都选择未选过的集合中的边最大的，知道最后所有点都是连通的。
发表于 2015-10-06 17:10:05 回复(0)
潜水系的徐先森头像 潜水系的徐先森
<p>无向图，矩阵对称，只需选择上三角选择最大权值，保证选择边，每行每列仅一个被选中。这些权值之和即为最大生成树权</p>
发表于 2020-12-21 14:54:50 回复(0)
前途光明头像 前途光明
不能直接套用用于生成MST的两个算法，那样就会得13。应该改进算法，起点的选择有讲究——选择权小的几个边所确定的（共同连接的）顶点作为起点。（本题应选择D） 以上仅为个人观点，不保证正确。
发表于 2018-11-29 17:49:14 回复(0)
黏黏糖头像 黏黏糖
使用Krustal算法或者Prime算法构造“”最大生成树”：即每次选择代价最大的边加入森林（Prime）；选择代价最大的边的两个顶点加入等价类（Krustal）
发表于 2017-05-09 10:46:34 回复(0)
牛客9712765号头像 牛客9712765号
发表于 2016-12-26 21:44:26 回复(1)
光明顶头像 光明顶
没做对的孩子们，你们的图论是不是和我一样忘了
发表于 2016-10-24 21:18:35 回复(0)
Echo001头像 Echo001
prim算法，每次选最大边
发表于 2016-08-09 12:13:07 回复(1)
逆袭的黑马头像 逆袭的黑马
不明白什么是最大生成树
发表于 2021-01-04 13:39:20 回复(0)
Lies_头像 Lies_
发表于 2022-11-07 19:04:16 回复(0)
辉小歌头像 辉小歌
最大生成树就是 权值和最大的树 和最小生成树完全相反。 如果这是一道算法题，且无负权边。那将边全部取负值用prim或克鲁斯卡尔跑一下最小生成树即可。最后记得取绝对值。
发表于 2022-08-21 14:43:53 回复(0)
MONSTERKHJSKDLJAS头像 MONSTERKHJSKDLJAS
无向图中的极大连通子图（maximal connected subgraph）称为原图的连通分量
补充：强连通图只有一个强连通分量，即本身；




发表于 2020-08-14 09:10:28 回复(0)
大黄蜂=_=头像 大黄蜂=_=

两个算法，prim算法和Kruskal算法


发表于 2019-10-28 21:10:02 回复(0)
我会回来的呢头像 我会回来的呢

个人觉得Prim算法也能得出来14


编辑于 2019-08-30 07:50:34 回复(0)
coderofUESTC头像 coderofUESTC
这题错误明显，“无身带权图”应该改为“无向带权图”，而且邻接矩阵的表示应该写成矩阵形式。
根据邻接矩阵画出图，选最长的边，边数最少就行了5+4+3+2=14；D
发表于 2015-07-31 19:03:10 回复(0)
提交观点

问题信息

谷歌 树 图
来自：Google2012笔试卷
上传者：forever_you
难度：
19条回答 23339浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号