普林斯顿公开课 算法1-7:并查集基本概念

本节讲的是并查集的基本概念。

算法的开发步骤

  1. 对问题进行数学建模
  2. 寻找一个能够解决问题的算法
  3. 运行算法检测速度和内存是否符合要求
  4. 如果达不到要求,找出原因
  5. 寻找一种方法来解决问题
  6. 循环步骤,直到满意为止

以上就是算法开发比较科学的方法。算法开发完成之后需要进行数学分析。

并查集问题

给定N个物体,可以提供两种操作,一种是合并操作,一种是查找操作。合并操作就是将两个节点进行连接,查找操作就是判断两个节点是否连接在一起。

应用中的物体类型

实际应用中,并查集算法可以支持各种各样的物体类型,比如:

  • 图片中的像素
  • 网络中的计算机
  • 社交网络中的用户
  • 计算机芯片中的晶体管
  • 数学集合中的元素
  • 程序中的变量名称
  • 化合物中的金属离子

实际应用中,为了避免无关因素的干扰,通常需要将具体的物体进行编号,在计算的时候只需要对整数进行操作即可。

连接的性质

节点之间的连接具有三种性质:

  • 反射性:每个节点和自己总是相连的
  • 对称性:如果p连接q,q也连接p
  • 传递性:如果p连接q,q连接r,那么p也连接r

连接部件

概念:相连的节点所组成的集合。

下图展示了连接部件:

操作

并查集提供两种操作:

  • 查找操作:检测两个节点是否相连
  • 合并操作:将两个节点进行连接

目标

并查集算法需要实现以下目标:

  • 对象的数量N可以非常大
  • 操作次数M可以非常大
  • 查找和合并两种操作可以随意调用

普林斯顿公开课 算法1-7:并查集基本概念,布布扣,bubuko.com

时间: 05-29

普林斯顿公开课 算法1-7:并查集基本概念的相关文章

普林斯顿公开课 算法1-10:并查集-优化的快速合并方法

应用 渗透问题 游戏中会用到. 动态连接 最近共同祖先 等价有限状态机 物理学Hoshen-Kopelman算法:就是对网格中的像素进行分块 Hinley-Milner多态类型推断 Kruskai最小生成树 Fortran等价语句编译 形态学开闭属性 Matlab中关于图像处理的bwlabel函数 渗透问题 一个N×N的矩阵,判断顶部和底部是否连通就是渗透问题. 下图中左侧的矩阵能渗透,右侧矩阵不能渗透. 渗透问题在电学.流体力学.社会交际中都有应用. 在游戏中可能需要生成一张地图,但是作为地图

普林斯顿公开课 算法1-11:并查集的应用

应用 渗透问题 游戏中会用到. 动态连接 最近共同祖先 等价有限状态机 物理学Hoshen-Kopelman算法:就是对网格中的像素进行分块 Hinley-Milner多态类型推断 Kruskai最小生成树 Fortran等价语句编译 形态学开闭属性 Matlab中关于图像处理的bwlabel函数 渗透问题 一个N×N的矩阵,判断顶部和底部是否连通就是渗透问题. 下图中左侧的矩阵能渗透,右侧矩阵不能渗透. 渗透问题在电学.流体力学.社会交际中都有应用. 在游戏中可能需要生成一张地图,但是作为地图

普林斯顿公开课 算法1-8:并查集 快速查找

本节讲的是并查集的第一种实现方法,这种方法查找操作开销很小而合并操作开销比较大. 数据结构 假设有N个节点,那么该算法的数据结构就是一个包含N个整数的数组id[]. 判断操作 判断节点p和节点q是否相连就是判断id[p]和id[q]的值是否一致. 合并操作 合并节点p和节点q就是将id数组中所有的id[p]都修改为id[q]. 这样的话,每次合并都要遍历整个数组,修改多个值,因此开销比较大. 复杂度 合并一次的复杂度是N,如果需要合并N次,那么整个程序的复杂度就是N^2.这样的复杂度不适合应用于

普林斯顿公开课 算法1-9:并查集-快速合并

本节讲的是并查集的另外一种实现方法.这种方法的合并操作开销很小,但是查找操作开销很大. 数据结构 这种算法的数据结构和快速查找方法的数据结构是一样的,也是N个整数组成的数组. 数组中每个元素id[i]的含义是指i的上级是id[i]. 根节点 一个节点的根节点就是id[id[id[...id[i]....]]],一直循环直到数值不再变化为止.由于算法的特性,这种循环永远不会造成死循环. 查找操作 查找操作就是判断两个节点的根节点是否相同. 合并操作 合并节点p和节点q就是将p节点的根节点的父节点设

普林斯顿公开课 算法1-9:并查集-高速合并

本节讲的是并查集的第二种实现方法.这样的方法的合并操作开销非常小,可是查找操作开销非常大. 数据结构 这样的算法的数据结构和高速查找方法的数据结构是一样的,也是N个整数组成的数组. 数组中每一个元素id[i]的含义是指i的上级是id[i]. 根节点 一个节点的根节点就是id[id[id[...id[i]....]]],一直循环直到数值不再变化为止.因为算法的特性,这样的循环永远不会造成死循环. 查找操作 查找操作就是推断两个节点的根节点是否同样. 合并操作 合并节点p和节点q就是将p节点的根节点

普林斯顿公开课 算法2-1:排序概述

目标 对所有类型的数据进行排序. 问题 排序函数如何知道比较的是哪种类型的数据呢? 回调函数 这时候就需要引入回调函数的概念了.回调函数就是将可执行的代码作为参数进行传递. 实现回调的方法 在Java中可以通过接口来实现,在C语言中可以通过函数指针来实现,C++中可以通过class-type functor,也就是重载操作符operator ()的类,在C#中可以使用Delegate委托,在Python/Perl/ML/javascript中可以直接传递函数. JDK中提供了Comparable

普林斯顿公开课 算法1-1:算法分析

为什么要分析算法 分析算法能够预測算法的性能,比較算法之间的优劣,保证算法的正确性,理解算法的理论基础. 成功算法的样例 离散傅立叶变换,假设使用暴力方法,那么算法的复杂度是是N^2,假设使用FFT高速傅立叶变换能够实现O(N logN)复杂度 N-body模拟:使用Barnes-hut算法能够将复杂度减少到N logN 顺便发一张N-body模拟的炫图 Barnes-Hut算法示意图 算法分析的步骤 观察问题的特征和想到得到的结果 依据观察结果提出如果 使用如果来预測可能发生的情况 检測预測结

普林斯顿公开课 算法1-2:观察

这章通过一个简单的例子,详细说明算法分析的步骤. 算法 问题 给定N个不同的整数,从中任意取出三个整数.请问有几种情况,使得取出的3个整数之和为0? 解法 可以使用暴力算法,代码如下: 1 2 3 4 5 6 7 8 9 for(int i=0;i<N;i++){     for(int j=0;j<N;j++){         for(int k=0;k<N;k++){             if(a[i]+b[i]+a[k]==0){                 count+

普林斯顿公开课 算法1-3:数学模型

本节主要通过建立数学模型,来计算算法的运行时间. 公式 算法的运行时间=所有操作的开销乘以操作的次数之和 开销 下表展示了各种操作所需要的时间(单位:纳秒) 整数加法 2.1 整数乘法 2.4 整数除法 5.4 浮点加法 4.6 浮点乘法 4.2 浮点除法 13.5 sin 91.3 arctan 129.0 举例 问题 计算数据中0的个数 代码 1 2 3 4 int count = 0; for (int i= 0; i < N; i++)     if (a[i] == 0)