栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构之并查集

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构之并查集

基于高度优化的并查集
public class UnionFind1 {
	private int[] parent;
	private int[] high;

	public UnionFind1(int size) {
		high = new int[size];
		parent = new int[size];
		for (int i = 0; i < size; i++) {
			high[i] = 1;
			parent[i] = i;
		}
	}

	public boolean isConnected(int firstElement, int secondElement) {
		return find(firstElement) == find(secondElement);
	}

	public int find(int element) {
		while (element != parent[element]) {
            // 要找element最终的老大哥,不等,则不断更新
			element = parent[element];
		}
		return element;
	}

	public void UnionElements(int firstElement, int secondElement) {
		int firstRoot = find(firstElement);
		int secondRoot = find(secondElement);
		if (firstRoot == secondRoot)
			return;
		if (high[firstRoot] > high[secondRoot])
			parent[secondRoot] = firstRoot;
		else if (high[firstRoot] < high[secondRoot])
			parent[firstRoot] = secondRoot;
		else {
			parent[secondRoot] = firstRoot;
			high[firstRoot] += 1;
		}
	}
}
基于重量(孩子节点个数)优化的并查集
public class UnionFind2 {	
	private int[] parent;
	private int[] weight;
	
	public UnionFind2(int size) {
		this.parent = new int[size];
		this.weight = new int[size];
		for (int i = 0; i < size; i++) {
			this.parent[i] = i;
			this.weight[i] = 1;
		}
	}

	public int find(int element) {
		while (element != parent[element]) {
			// 当前结点指向自己父亲的父亲,减少深度
			parent[element] = parent[parent[element]];
			element = parent[element];
		}
		return element;
	}

	public boolean isConnected(int firstElement, int secondElement) {
		return find(firstElement) == find(secondElement);
	}

	public void unionElements(int firstElement, int secondElement) {
		int firstRoot = find(firstElement);
		int secondRoot = find(secondElement);

		// 如果已经属于同一个集合了,就不用再合并了。
		if (firstRoot == secondRoot) {
			return;
		}

		if (weight[firstRoot] > weight[secondRoot]) {
			parent[secondRoot] = firstRoot;
			weight[firstRoot] += weight[secondRoot];
		} else {// weight[firstRoot] <= weight[secondRoot]
			parent[firstRoot] = secondRoot;
			weight[secondRoot] += weight[firstRoot];
		}
	}
}
并查集的应用 畅通工程

某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?

思路: 在并查集中进行合并操作,求出最后剩下多少个组(集合)。这些组之间是互相不可达的。假如有M个组,那其实再需要M-1条连线就可以把他们连接起来了。所以组数 - 1 就是最后答案。(原先每个元素自成一组,每执行一次合并操作,组数减一)

public UnionFind(int size) {
	parent = new int[size];
	weight = new int[size];
	this.group = size;

	for (int i = 0; i < size; i++) {
		parent[i] = i;
		weight[i] = 1;
	}
}
 public void UnionElement(int firstElement, int secondElement) {
	int firstRoot = find(firstElement);
	int secondRoot = find(secondElement);

	if (firstRoot == secondRoot)
		return;             

	if (weight[firstRoot] > weight[secondRoot]) {  // 谁的孩子多谁就是新的根节点
		parent[secondRoot] = firstRoot;
		weight[firstRoot] += weight[secondRoot];
	} else {
		parent[firstRoot] = secondRoot;
		weight[secondRoot] += weight[firstRoot];
	}

	this.group--; // 每进行一次合并操作,集合个数减一
}
岛屿数量

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。链接:https://leetcode-cn.com/problems/number-of-islands

题目大致意思是: 在二维矩阵中,搜索一共有多少个连通域('1’表示可达,即连通,此处是4连通域)

思路: 属于一个连通域,即所含元素均属于同一个集合。采用并查集,统计网格中‘1’的个数,当做初始集合个数,‘1’对应的存储下标即为各自初始根节点。当前若遍历到‘1’则与它的4连通域元素进行合并操作,每进行一次合并,集合总数减一。最后连通域的个数即为集合的个数。

public NumOfLands(char[][] grid) {
	this.group = 0;
	int row = grid.length;
	int col = grid[0].length;

	this.parent = new int[row * col];
	this.weight = new int[row * col];
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (grid[i][j] == '1') {
				parent[i * col + j] = i * col + j;  // 1 对应的存储下标值当做其根节点
				group++;
				weight[i * col + j] = 1;
			}
		}
	}
}

public int numIslands(char[][] grid) {
	if (grid == null || grid.length == 0)
		return 0;

	int R = grid.length, C = grid[0].length;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (grid[i][j] == '1') {
				grid[i][j] = '0';

				if (i - 1 >= 0 && grid[i - 1][j] == '1') {
					unionElements(i * C + j, (i - 1) * C + j);
				}
				if (i + 1 < R && grid[i + 1][j] == '1') {
					unionElements(i * C + j, (i + 1) * C + j);
				}
				if (j - 1 >= 0 && grid[i][j - 1] == '1') {
					unionElements(i * C + j, i * C + j - 1);
				}
				if (j + 1 < C && grid[i][j + 1] == '1') {
					unionElements(i * C + j, i * C + j + 1);
				}
			}
		}
	}

	return getGroup();
}
最短的桥

在给定的二维二进制数组 A 中,存在两座岛。(岛是由四面相连的 1 形成的一个最大组。)现在,我们可以将 0 变为 1,以使两座岛连接起来,变成一座岛。返回必须翻转的 0 的最小数目。(可以保证答案至少是 1 。)链接:https://leetcode-cn.com/problems/shortest-bridge

题目大意: 就是网格中有两个由’1’构成的连通域,让找到使两个连通域成为一个连通域的最少操作数是多少(即将0变1的最少次数)

public class 最短的桥 {
	
	public static int shortestBridge(int[][] A) {
		int R = A.length, C = A[0].length;
		int[][] colors = dfs(A);

		Queue queue = new LinkedList();
		Set target = new HashSet();

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (colors[r][c] == 1)
					queue.offer(new Node(r, c, 0));
				else if (colors[r][c] == 2)
					target.add(r * C + c);  // 目标点坐标(目标点不止一个)
			}
		}

		while (!queue.isEmpty()) {
			Node node = queue.poll();
			if (target.contains(node.r * C + node.c))
				return node.depth - 1;

			for (int k : neighbors(A, node.r, node.c)) {
				int nr = k / C, nc = k % C;
				if (colors[nr][nc] != 1) { 
					queue.add(new Node(nr, nc, node.depth + 1));
					colors[nr][nc] = 1; // 切记要将访问过的标记成不可再访问
				}
			}
		}
		return 0;
	}

	public static int[][] dfs(int[][] A) {   // 使用栈进行模拟
		int R = A.length, C = A[0].length;
		int[][] colors = new int[R][C];

		int t = 0; // 为每个连通域打上一个标记

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (colors[r][c] == 0 && A[r][c] == 1) {
					
					Deque stack = new ArrayDeque();
					stack.push(r * C + c);
					colors[r][c] = ++t;

					while (!stack.isEmpty()) {
						int id = stack.pop();
						int row = id / C, col = id % C;
						for (int k : neighbors(A, row, col)) {
							int nr = k / C, nc = k % C;
							if (A[nr][nc] == 1 && colors[nr][nc] == 0) {
								colors[nr][nc] = t;
								stack.push(nr * C + nc);
							}
						}
					}
				}
			}
		}
		return colors;
	}

	public static List neighbors(int[][] A, int r, int c) {
		int R = A.length, C = A[0].length;
		List ans = new ArrayList();
		if (0 <= r - 1)
			ans.add((r - 1) * R + c);
		if (0 <= c - 1)
			ans.add(r * R + (c - 1));
		if (r + 1 < R)
			ans.add((r + 1) * R + c);
		if (c + 1 < C)
			ans.add(r * R + (c + 1));
		return ans;
	}
}


class Node {
	int r, c, depth;

	public Node(int r, int c, int depth) {
		this.r = r;
		this.c = c;
		this.depth = depth;
	}
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/975386.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号