kruskal

# kruskal算法及其简单优化 ## 写在前面 - ~~~最近重学了noip的部分相关图论算法 不定期update~~ 在学习之前 我们先来看几个概念 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等函数实现 如有特殊操作 可重载运算符 第二个操作 当然可以用**并查集**啦！ 可爱的冰茶姬要登场喽！ ### 并查集