DreamJudge1312_kruskal算法
推荐阅读
- Kruskal 求解的是全图连通的最低成本，即使为了保证图中的任意两点连通，所需要的最小花费
- Kruskal = 贪心策略 + 并查集
- 其实Kruskal 就是利用了并查集的特点，并查集可以通过输入的边来判断其是否为连通图所必要的边，如果是那么进行连接，不必要掠过
- 如果再将输入边的权值按从小到大排列，那么并查集记录的就是使图联通的必要的最小边的集合，即最小生成树，其权值和即为所求
- sum 记录权值和，total 记录 输入边中为必要的连通的边为多少，若 total < N -1 ，那么图不连通，就更谈不上最小生成树
- 注意：并查集：find() 初始化，连通边 ，+ 排序 = Kruskal
- 其实相对于并查集，Kruskal 就是 定义了一个数据结构，记录权值，并按权值进行排序，再根据顺序输入并查集连通边的判断
- 适合于边少的 M logM
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发