这是一位 google 工程师分享的8小时的数据结构的视频,我的笔记
Union Find
- keep track of elements in different sets
- primary operations:
findandunion
Usage
- Kruskal's
minimum spanning treealgorithm - Grid percolation
- Network connectivity
- Least common ancestor in trees
- Image processing
Complexity
- construction: O(n)
- union/join/size/check connected/:
(n) :接近常量时间
- count: O(1)
给定一个无向图，如果它任意两个顶点都联通并且是一棵树，那么我们就称之为生成树(Spanning Tree)。如果是带权值的无向图，那么权值之和最小的生成树，我们就称之为最小生成树(MST, Minimum Spanning Tree)。
-> 用最少的边连接所有的顶点
- sort edges by ascending edge weight
- walk through edges
- 检查顶点，如果两个顶点都已经unified，就忽略
- 其实就是这两个点分别被别的边连过了
- 否则就添加edge，并且unify顶点
- 检查顶点，如果两个顶点都已经unified，就忽略
看到这里，首先想知道什么是unified，看实现，也就是在一个集合里(component)
image.png
观察C_J，因为C和J已经在一个组里了，这条边就不需要了
-
观察D_E，一旦连上后，紫色和绿色其实就是一个组了
image.png 观察D_H，一旦连上后，紫色和红色也成为了一个组
连接B_C，所有顶点就全部连上了，并且只有一条紫线
Find: 找元素在哪个component里，然后找到它的root
Union: 找两个元素分别在哪个component里，然后找到它们的root，如果不是同一个root，就让其中一个成为另一个的parent
- component的个数与root的个数一致
- root的个数只减不增（因为通常只合并而不拆分）
union find里
- 为每个元素分配一个索引，每个元素指向自己（即初始是n个root，n个component)
- 描述两两之间的关系，以任一元素为parent （谁来描述？）
- 有一个元素已经属于别的component里的，就将它也加到那个component里去
- 如果这个元素也是别的component里的顶点，就把整个组指向另一个组的root
Path Compression Union Find
image.png
由一层层找到root改为所有顶点直接指向顶点（星形结构），实现路径压缩
这段代码演示的是，查找p的root节点，在查找的过程中，顺便进行了路径压缩
image.png
合并的逻辑就是比较谁的元素多就把谁当作root，另一个component的root的parent设为元素多的组的root
合并完成后组数就少了1
image.png
看代码，这一步里面并没有路径压缩，也就是小组里面的元素并没有进一步再星状地指向新的parent，仍然指向的是老的组的root。
