kruskal

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. 在E中选择一条具有最小权植的边 若该边的两个顶点落在不同的连通分量上 则将此边加入到T中 否则 即这条边的两个顶点落到同一连通分量上 则将此边舍去(此后永远不再选用这条边) 重新选择一条权植最小的边
  3. 重复这个过程,直到T中G的所有顶点都在一个连通分量上

图片来源于互联网

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

查询与合并操作

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

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

可爱的冰茶姬要登场喽!

并查集


发表于 2018-10-11 16:13:44 in 数据结构