网页的依托网站,推广普通话黑板报内容,焦点网站设计,做外贸网站代理商并查集介绍和常用模板
前言#xff1a;
并查集#xff08;Union-find set 也叫Disjoint Sets#xff09;是图论里面一种用来判断节点之间是否连通的数据结构#xff0c;学会使用它可以处理一些跟节点连通性的问题。它有两个很重要的方法#xff1a; Find(x)#xff1a;…并查集介绍和常用模板
前言
并查集Union-find set 也叫Disjoint Sets是图论里面一种用来判断节点之间是否连通的数据结构学会使用它可以处理一些跟节点连通性的问题。它有两个很重要的方法 Find(x)查找x的父元素 Union(x,y)将xy两个对应的集合合并到一起
接下来我们先看一个例子看看怎么判断节点之间是否相连怎么把两个集合合并到一起: 先看第一个问题怎么判断两个节点是否相连
在上面这张图里面我们肉眼可以看到0,1,2是连在一起3,4是连在一起5是单独存在的这也是前置客观存在的条件。
那么我们怎么判断0和3是不是连到一起了呢思路是这样我们把这三块看成是三个团队0,1,2是一个团队队长是03,4是一个团队队长是35是一个团队队长是5。判断逻辑是两个元素的队长是相同的就认为在一个团队里面。所以更加计算机化的语言描述是三个集合每个集合都有一个根节点如果根节点是相同的就是在一个集合里面。因此你要想到我们需要存储每个节点对应的根节点这样才能判断出两个节点是否在同一个集合内。
再看第二个问题怎么将两个集合合并
看过问题一后你可能就已经有一些思路了既然只要是根节点相同就是同一个集合判断是否相连那么我是不是合并两个集合的时候只要根节点改成同一个就行了没错就是这样。合并的时候就把某个集合的根节点改成另外一个集合的根节点就行了。这里引申出一个问题应该把哪个集合的根节点修改掉后面我们讲到按照秩来合并集合的时候会讲到一般情况随便用哪个集合的根节点都可以。
并查集常用模板
1.QuickFind:
我们直接快进到代码部分因为有了前面的例子的铺垫再来讲代码应该就比较好理解了说明我都放到代码的注释里面了。
public class UnionFind1 {// 首先我们创建了一个数组 用来保存每个元素的根节点public int root[];// 然后我们根据元素的数量 初始化数组数组的下标就是节点数组的值就是元素i的根节点一开始每个元素的根节点都是自己public UnionFind1(int size) {root new int[size];for (int i 0; i size; i) {root[i] i;}}// find找根节点直接返回x对应的根节点root[x]public int find(int x) {return root[x];}// union合并两个元素xypublic void union(int x, int y) {// 先找到各自的根节点 一开始都是元素自己int rootX find(x);int rootY find(y);if (rootX ! rootY) {// 因为两个根节点不一样 所以我们随便取一个元素的根节点作为新的根节点// 这里取的rootX为新的根节点然后把原来所有根节点是rootY的都修改为rootXfor (int i 0; i root.length; i) {if (root[i] rootY) {root[i] rootX;}}}};// 判断两个元素是否相连 其实就是判断根节点是否相同 是对find()的一种运用public boolean connected(int x, int y) {return find(x) find(y);}public static void main(String[] args) throws Exception {// 下面的例子就更好理解了我们先初始化并查集一共6个元素就是上面图中的元素// 在图中的连接情况 把0,1,2连起来3,4连起来并用connected()测试下元素的连通性// 最后我们把元素5加入到1的集合中测试下2和5的连通性发现确实2和5也相连了程序测试完成。UnionFind1 uf new UnionFind1(6);// 0-1-2 3-4 5uf.union(0, 1);uf.union(0, 2);uf.union(3, 4);// trueSystem.out.println(uf.connected(1, 2));// falseSystem.out.println(uf.connected(1, 3));// falseSystem.out.println(uf.connected(4, 5));// 0-1-2 3-4 5uf.union(1, 5);// trueSystem.out.println(uf.connected(2, 5));}
}
这个模板为什么要叫QuickFind呢因为这个模板的find方法比较快是O(1)的时间复杂度但是union方法就比较麻烦得元素都遍历一遍复杂度是O(N)
2.QuickUnion
quickUnion主要是union的操作比较快直接将x,y元素中任意一个元素变成另外一个元素的爸爸操作是O(1)但是要找根节点的时候就毕竟慢得一直往上找直到是根节点为止。
public class UnionFind2 {public int[] root;public UnionFind2(int size) {root new int[size];for (int i 0; i size; i) {root[i] i;}}public int find(int x) {while (root[x] ! x) {return root[x] find(root[x]);}return x;}public void union(int x, int y) {int xRoot find(x);int yRoot find(y);if (xRoot ! yRoot) {root[yRoot] xRoot;}}public boolean connected(int x, int y) {return find(x) find(y);}public static void main(String[] args) throws Exception {// 下面的例子就更好理解了我们先初始化并查集一共6个元素就是上面图中的元素// 在图中的连接情况 把0,1,2连起来3,4连起来并用connected()测试下元素的连通性// 最后我们把元素5加入到1的集合中测试下2和5的连通性发现确实2和5也相连了程序测试完成。UnionFind2 uf new UnionFind2(6);// 0-1-2 3-4 5uf.union(0, 1);uf.union(0, 2);uf.union(3, 4);// trueSystem.out.println(uf.connected(1, 2));// falseSystem.out.println(uf.connected(1, 3));// falseSystem.out.println(uf.connected(4, 5));// 0-1-2 3-4 5uf.union(1, 5);// trueSystem.out.println(uf.connected(2, 5));}
}3.按秩合并的QuickUnion
public class UnionFind3 {// 在QuickUnion的基础上增加了rank数组来记录int root[];int rank[];// 初始化的时候rank默认都是1public UnionFind3(int size) {root new int[size];rank new int[size];for (int i 0; i size; i) {root[i] i;rank[i] 1;}}public int find(int x) {while (x ! root[x]) {x root[x];}return x;}// 如果两个元素的秩相同就随机取一个元素为秩更大的 否则就是谁的秩大 谁就是爸爸public void union(int x, int y) {int rootX find(x);int rootY find(y);if (rootX ! rootY) {if (rank[rootX] rank[rootY]) {root[rootY] rootX;} else if (rank[rootX] rank[rootY]) {root[rootX] rootY;} else {root[rootY] rootX;rank[rootX] 1;}}}public boolean connected(int x, int y) {return find(x) find(y);}public static void main(String[] args) throws Exception {// 下面的例子就更好理解了我们先初始化并查集一共6个元素就是上面图中的元素// 在图中的连接情况 把0,1,2连起来3,4连起来并用connected()测试下元素的连通性// 最后我们把元素5加入到1的集合中测试下2和5的连通性发现确实2和5也相连了程序测试完成。UnionFind3 uf new UnionFind3(6);// 0-1-2 3-4 5uf.union(0, 1);uf.union(0, 2);uf.union(3, 4);// trueSystem.out.println(uf.connected(1, 2));// falseSystem.out.println(uf.connected(1, 3));// falseSystem.out.println(uf.connected(4, 5));// 0-1-2 3-4 5uf.union(1, 5);// trueSystem.out.println(uf.connected(2, 5));}
}4.路径压缩的QuickUnion
public class UnionFind4 {int root[];public UnionFind4(int size) {root new int[size];for (int i 0; i size; i) {root[i] i;}}// 优化点在这里 再查找父节点的同时会把根节点赋值给递归过程的其他元素public int find(int x) {if (x root[x]) {return x;}return root[x] find(root[x]);}public void union(int x, int y) {int rootX find(x);int rootY find(y);if (rootX ! rootY) {root[rootY] rootX;}};public boolean connected(int x, int y) {return find(x) find(y);}public static void main(String[] args) throws Exception {// 下面的例子就更好理解了我们先初始化并查集一共6个元素就是上面图中的元素// 在图中的连接情况 把0,1,2连起来3,4连起来并用connected()测试下元素的连通性// 最后我们把元素5加入到1的集合中测试下2和5的连通性发现确实2和5也相连了程序测试完成。UnionFind4 uf new UnionFind4(6);// 0-1-2 3-4 5uf.union(0, 1);uf.union(0, 2);uf.union(3, 4);// trueSystem.out.println(uf.connected(1, 2));// falseSystem.out.println(uf.connected(1, 3));// falseSystem.out.println(uf.connected(4, 5));// 0-1-2 3-4 5uf.union(1, 5);// trueSystem.out.println(uf.connected(2, 5));}
}5.按秩Union并且路径压缩
这个没有太多要说的就是3,4模板和合并可以同时解决查询慢和防止并查集变成链表的情况。
public class UnionFind5 {private int[] root;private int[] rank;public UnionFind5(int size) {root new int[size];rank new int[size];for (int i 0; i size; i) {root[i] i;rank[i] 1;}}public int find(int x) {if (x root[x]) {return x;}return root[x] find(root[x]);}public void union(int x, int y) {int rootX find(x);int rootY find(y);if (rootX ! rootY) {if (rank[rootX] rank[rootY]) {root[rootY] rootX;} else if (rank[rootX] rank[rootY]) {root[rootX] rootY;} else {root[rootY] rootX;rank[rootX] 1;}}}public boolean connected(int x, int y) {return find(x) find(y);}public static void main(String[] args) throws Exception {// 下面的例子就更好理解了我们先初始化并查集一共6个元素就是上面图中的元素// 在图中的连接情况 把0,1,2连起来3,4连起来并用connected()测试下元素的连通性// 最后我们把元素5加入到1的集合中测试下2和5的连通性发现确实2和5也相连了程序测试完成。UnionFind5 uf new UnionFind5(6);// 0-1-2 3-4 5uf.union(0, 1);uf.union(0, 2);uf.union(3, 4);// trueSystem.out.println(uf.connected(1, 2));// falseSystem.out.println(uf.connected(1, 3));// falseSystem.out.println(uf.connected(4, 5));// 0-1-2 3-4 5uf.union(1, 5);// trueSystem.out.println(uf.connected(2, 5));}
}用并查集解决问题
这里我们来看一道用并查集解决的算法题leetcode-200岛屿数量
给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。示例 1输入grid [[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]
]
输出1
示例 2输入grid [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]
]
输出3提示m grid.length
n grid[i].length
1 m, n 300
grid[i][j] 的值为 0 或 1这道题目可以用bfs/dfs解决也可以用并查集因为我们刚学习完并查集所以就学以致用。
解题思路
遍历整个图将是邻近的岛屿元素全部用并查集连起来也就是把1连起来最后统计parent有多少个就是有多少岛屿不过这道题m*n比较大遍历会超时。当然我们也可以在union的时候判断出岛屿的数量最后直接返回。 class UnionFind {public int root[];// 用来统计最后有多少个岛屿int num;public UnionFind(char[][] grid) {int row grid.length;int col grid[0].length;root new int[row * col];for (int r 0; r row; r) {for (int c 0; c col; c) {if (grid[r][c] 1) {// 如果是岛屿的话 num就增加num;// 将二维坐标准换为一维的root[r * col c] r * col c;}}}}// 优化点在这里 再查找父节点的同时会把根节点赋值给递归过程的其他元素public int find(int x) {if (x root[x]) {return x;}return root[x] find(root[x]);}public void union(int x, int y) {int rootX find(x);int rootY find(y);if (rootX ! rootY) {root[rootY] rootX;num--;}}}public int numIslands(char[][] grid) {int row grid.length;int col grid[0].length;UnionFind uf new UnionFind(grid);int sea 0;for (int r 0; r row; r) {for (int c 0; c col; c) {if (grid[r][c] 1) {// 处理完之后 赋值为另外一个值 这样下次就不会重复遍历到这个值grid[r][c] 0;if (r - 1 0 grid[r - 1][c] 1) {uf.union(r * col c, (r - 1) * col c);}if (r 1 row grid[r 1][c] 1) {uf.union(r * col c, (r 1) * col c);}if (c - 1 0 grid[r][c - 1] 1) {uf.union(r * col c, r * col c - 1);}if (c 1 col grid[r][c 1] 1) {uf.union(r * col c, r * col c 1);}}}}return uf.num;}Testpublic void test1() {Assert.assertEquals(3, numIslands(new char[][]{new char[]{1, 1, 0, 0, 0},new char[]{1, 1, 0, 0, 0},new char[]{0, 0, 1, 0, 0},new char[]{0, 0, 0, 1, 1}}));Assert.assertEquals(1, numIslands(new char[][]{new char[]{1, 1, 1},new char[]{0, 1, 0},new char[]{1, 1, 1},}));}
