首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
用克鲁斯卡尔算法将下列的图构造成最小生成树,画出生成过程。
[问答题]
用克鲁斯卡尔算法将下列的图构造成最小生成树,画出生成过程。
添加笔记
求解答(1)
邀请回答
收藏(4)
分享
纠错
2个回答
添加回答
0
张小头
取n个顶点且无边的非连通图T={V,{}},此时每个顶点自成一个连通分量。
按照规则:
1.每次从小到大选取权值最小的边,该边的两个顶点满足在不同的连通分量上,加入到T中
2.当选取的边连接的两个顶点在同一个连通分量的时候,舍弃该边,选取权值相同或者次小的满足条件1的边
(这里需要搞懂连通分量的概念,这里取自百度:在无向图中,如果从顶点vi到顶点vj有路径,则称vi和vj连通。如果图中任意两个顶点之间都连通,则称该图为连通图,否则,将其中的较大连通子图称为连通分量。 在有向图中,如果对于每一对顶点vi和vj,从vi到vj和从vj到vi都有路径,则称该图为强连通图;否则,将其中的极大连通子图称为强连通分量。)
比如为什么不选取2-5这条边,因为0-5 0-2这两条边已经连上了,2可以通过0到5,所以2和5连通,属于同一个连通分量,所以在1-5 2-5 的选择中,就舍弃2-5这条边。
发表于 2021-02-19 18:53:07
回复(0)
0
杨😗
Kruskal算法,每次找最小边加入边集即可
发表于 2020-04-27 16:57:01
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
树
上传者:
城市里的养猫者
难度:
2条回答
4收藏
2945浏览
热门推荐
相关试题
假定一个待哈希存储的线性表为(32...
哈希
评论
(1)
5.下列判断正确的是( )
资料分析
言语理解与表达
资料分析
评论
(1)
《拳皇97》最后BOSS是谁?
游戏常识
评论
(1)
《魔兽世界》中,下列不属于玩家可以...
游戏常识
评论
(1)
你有没有崇拜的偶像,你欣赏他/她身...
通用能力
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题