19-大数据一班-杨文冠的博客

KD-Graph

思路：按边权由小到大合并边的两个顶点，假设当前需要操作的边为，则：如果和已经在同一个组里了就不用继续合并了如果和不在同一个组里，就将和所在的组合并，则到存在一条路径上的最大值就是，且找不到比其他的路径满足该路径上的最大值小于，因为和目前只有这一条路径(边)，那么每一阶段取出同权值的所有边，将这些边...

最小生成树

图的两个基本元素是点和边，与此对应，有两种方法可以构造最小生成树T。这两种算法都基于贪心算法，因为MST问题满足贪心算法的“最优性原理”，即全局最优包含局部最优。prim算法的原理是“最近的邻居一定在MST”上，kruskal算法的原理是“最短的边一定在MST上”。第一次出现kruskal算法或pr...

并查集

并查集的基本操作：1.find，查询一个元素属于哪一个集合。2.merge 把两个集合合并成一个大集合，一般不用写一个额外的函数，直接写主函数内就可以了。在并查集中，我们采用“待元法”，即为每个集合选择一个固定的元素，作为整个集合的“代表”。使用一个树形结构存储每个集合，书上每个结点都是一个元素，树...