首页> 算法/机器学习校招面试题目合集> Kruskal算法的基本过程
216

问答题 216 /376

Kruskal算法的基本过程

参考答案

参考回答:

Kruskal算法是以边为主导地位,始终选取当前可用的拥有最小权值的边,所选择的边不能构成回路。首先构造一个只有n个顶点没有边的非连通图,给所有的边按值以从小到大的顺序排序,选择一个最小权值边,若该边的两个顶点在不同的连通分量上,加入到有效边中,否则舍去这条边,重新选择权值最小的边,以此重复下去,直到所有顶点在同一连通分量上。
纠错 收藏
查看讨论
上一题 下一题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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