1. 并查集
2. 图

1. 介绍
2. 操作
3. 实现
4. 优化
5. 路径压缩
6. 复杂度

1. 并查集是一种树形结构
2. 并查集是为了高效解决连接问题
   • 判断网络中节点间的连接状态， 网络是个抽象概念，用户之间形成的网络
   • 数学中的集合类实现
3. 连接问题 和 路径问题
   • 比路径问题要回答的问题少
     • 和二分查找做比较
     • 和select做比较
     • 和堆作比较

1. 对于一组数据，主要支持两个操作
   • union(p, q)
   • find(p)
2. 用来回答一个问题
   • isConnected(p, q)

1. 并查集的使用普通数组实现

2. 并查集的使用parent指针数组实现

   • 将每个元素看作是一个节点， 使用指针指向父亲节点的树， 依然使用数组

1. 使用size数组优化
2. 使用rank数组优化

1. 节点p 指向 parent[p] 的 父节点 parent[parent[p]]，每次向上走两步
2. 使用递归，将每个节点不断向上查找parent[p]， 使得 p 指向根节点parent[p]，使得以parent[p]为根节点的高度为 2;

时间复杂度： 近乎是O(1)

1. 节点

2. 边

3. 应用场景

   1. 交通运输
   2. 社交网络
   3. 互联网
   4. 工作安排
   5. 脑区活动
   6. 程序执行状态

4. 图的分类

   • 从方向看
     1. 无向图 (是一种特殊的有向图)
     2. 有向图
   • 从权来看
     1. 有权图
     2. 无权图

5. 图的连通性

6. 简单图

   1. 自环边
   2. 平行边

7. 图的表示

   • 邻接矩阵， 适合稠密图(完全图)
   • 领接表， 适合稀疏图

8. 遍历邻边

   • 相邻节点迭代器

9. 图的遍历

   • 深度优先遍历， 求图中的连通分量， 寻路
   • 广度优先遍历， 最短路径(无权图)

10. 无权图的应用

• ps的魔棒，扫雷，（flood fill算法），连通分量
• 迷宫生成，迷宫本质是生成一棵树
• 欧拉路径
• 哈密尔顿路径
• 二分图
• 地图填色