是我太菜了
by 怪盗geek @ 2019-06-08 22:26:50
Kruskal 算法
Kruskal 算法是最小生成树算法的一种。算法过程如下：
首先我们定义带权无向图G的边集合为 E，接着我们再定义最小生成树的边集为 TT，初始集合 T=∅。接着执行以下操作：
1.首先，我们把图 G 看成一个有 n 棵树的森林，图上每个顶点对应一棵树；
2.接着，我们将边集 E 的每条边，按权值从小到大进行排序；
3.按边权从小到大的顺序遍历每条边 e = (u, v)，我们记顶点u所在的树为 T_u ，顶点 v 所在的树为 T_v，如果 T_u 和 T_v 不是同一棵树，则我们将边 e 加入集合 TT,并将两棵树 T_u和 T_v 进行合并；否则不进行任何操作。
算法执行完毕后，如果集合 T 包含 n-1 条边，则 T 就代表最小生成树中的所有边。
第三步操作需要对集合进行合并操作，因此要用并查集来维护。
by charliegong @ 2019-06-09 10:37:30
@[怪盗geek](/space/show?uid=80924)
by charliegong @ 2019-06-09 10:37:44
您还在吗
by charliegong @ 2019-06-09 13:10:33
@[charliegong](/space/show?uid=95626) 谢谢你，我后来用并查集重写了一遍就过了，原来那个代码找不出bug，可能逻辑上存在问题
by 怪盗geek @ 2019-06-09 16:42:35