Uniqueness of MST
思路分析
给定N个节点，M条边，每条边的端点以及边的权重已知，求最小生成树（MST）的权重，以及权重是否唯一，如果不存在最小生成树，则求有几个部分。
- 记录
M条边的信息 Kruskal's Algorithm求一个最小生成树MST，同时记录下最小生成树的所有节点（可以放入一个队列），权重weight，和所用的边数edges- 如果可以产生最小生成树，则进行
M-1次Kruskal's Algorithm，但是每次都要去掉一条边，这条边从步骤二中的最小生成树的节点队列中选取。如果可以生成一个新的最小生成树MST'，且权重和weight'等于步骤二中MST的权重weight，则最小生成树不唯一。 - 如果不存在最小生成树，则完全连接的部分有
N-edges个。
自测测试点
4 3
1 2 1
2 3 1
3 4 1
输出：
3
Yes
输入：
0 0
输出：
0
Yes
代码
待课程结束后看情况上传
最后
以上就是饱满火最近收集整理的关于FDS-HW10 Uniqueness of MST的全部内容，更多相关FDS-HW10内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复