kruskal算法及其简单优化

写在前面

在学习之前 我们先来看几个概念

1. 树：有很多神奇的性质 但其实就是个无环无向连通图 总点数n 总边数n-1
2. 最小生成树（MST）：无向连通图G的一个子图如果是一颗包含G的所有顶点的树，则该子图称为G的生成树。是连通图的极小连通子图。这里所谓极小是指：若在树中任意增加一条边，则将出现一条回路；若去掉一条边，将会使之变成非连通图 对无向连通图的生成树，各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。 即{T...}∈G MST=min T

算法

准则

1. 构成生成树的边必须来自原网格中
2. 仅能且必须使用n-1条边 来链接原图中n个节点
3. 不可加入可构成回路的边

这里不再讲解prim算法 ~因为我不会

主要来看kruskal算法

算法流程

思想基于贪心

设一个无向连通图G{V,E}（点集，边集）

1. 首先构造一个集合T{V，∅} 只有n个点没有边的集合 每个节点都处于一个只包含自己的联通子图中
2. 在Ｅ中选择一条具有最小权植的边 若该边的两个顶点落在不同的连通分量上 则将此边加入到Ｔ中 否则 即这条边的两个顶点落到同一连通分量上 则将此边舍去（此后永远不再选用这条边） 重新选择一条权植最小的边
3. 重复这个过程，直到T中G的所有顶点都在一个连通分量上

图片来源于互联网

刚才这一部分流程的讲解中 重要的两点是 一进行边权排序 二进行集合的

查询与合并操作

第一个操作可以通过stl中的sort等函数实现 如有特殊操作 可重载运算符

第二个操作 当然可以用并查集啦！

可爱的冰茶姬要登场喽！

并查集