Exemple d'analyse de union-find en Java
- WBOYavant
- 2023-04-27 19:46:041225parcourir
1. Présentation
Union-find : une structure de données de type arborescent utilisée pour résoudre certains problèmes de fusion et d'interrogation d'ensembles disjoints. Par exemple : il y a n villages, demandez s'il existe une route de liaison entre les deux villages, reliant les deux villages
Deux noyaux :
Find (Find) : Trouver l'ensemble où se trouve l'élément
Union (Union) : Combiner les deux Les ensembles d'éléments sont fusionnés en un seul ensemble
2. Implémentation de
Recherche d'union Il existe deux idées d'implémentation courantes
Recherche rapide
Complexité temporelle de la recherche : O(1)
Temps complexité de l'Union : O(n)
Union rapide
Complexité temporelle de la recherche : O(logn) peut être optimisé en O(a (n))a(n)
Time complexité de l'Union : O(logn) peut être optimisé en O(a(n))a(n)
en utilisant Le tableau implémente une structure arborescente, l'indice du tableau est l'élément et la valeur stockée dans le tableau est la valeur du nœud parent
Créer la classe abstraite Union Find
public abstract class UnionFind {
int[] parents;
/**
* 初始化并查集
* @param capacity
*/
public UnionFind(int capacity){
if(capacity < 0) {
throw new IllegalArgumentException("capacity must be >=0");
}
//初始时每一个元素父节点（根结点）是自己
parents = new int[capacity];
for(int i = 0; i < parents.length;i++) {
parents[i] = i;
}
}
/**
* 检查v1 v2 是否属于同一个集合
*/
public boolean isSame(int v1,int v2) {
return find(v1) == find(v2);
}
/**
* 查找v所属的集合 （根节点）
*/
public abstract int find(int v);
/**
* 合并v1 v2 所属的集合
*/
public abstract void union(int v1, int v2);
// 范围检查
public void rangeCheck(int v) {
if(v<0 || v > parents.length)
throw new IllegalArgumentException("v is out of capacity");
}
}2.1 Implémentation de la recherche rapide
Recherche d'union implémentée avec Quick Find, tree La hauteur maximale de Lorsque l'arbre est déséquilibré
Il existe deux idées d'optimisation : l'optimisation du classement et l'optimisation de la taille
3.1 Optimisation basée sur la taille
public class UnionFind_QF extends UnionFind {
public UnionFind_QF(int capacity) {
super(capacity);
}
// 查
@Override
public int find(int v) {
rangeCheck(v);
return parents[v];
}
// 并 将v1所在集合并到v2所在集合上
@Override
public void union(int v1, int v2) {
// 查找v1 v2 的父（根）节点
int p1= find(v1);
int p2 = find(v2);
if(p1 == p2) return;
//将所有以v1的根节点为根节点的元素全部并到v2所在集合上 即父节点改为v2的父节点
for(int i = 0; i< parents.length; i++) {
if(parents[i] == p1) {
parents[i] = p2;
}
}
}
}
Optimisation basée sur la taille Cela peut également provoquer l'arbre être déséquilibré3.2 Optimisation basée sur le classement
Idée de base : greffer un arbre court sur un grand arbre
public class UnionFind_QU extends UnionFind {
public UnionFind_QU(int capacity) {
super(capacity);
}
//查某一个元素的根节点
@Override
public int find(int v) {
//检查下标是否越界
rangeCheck(v);
// 一直循环查找节点的根节点
while (v != parents[v]) {
v = parents[v];
}
return v;
}
//V1 并到 v2 中
@Override
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if(p1 == p2) return;
//将v1 根节点 的 父节点 修改为 v2的根结点 完成合并
parents[p1] = p2;
}
}Basé sur l'optimisation du classement, à mesure que le nombre d'unions augmente, la hauteur de l'arbre deviendra de plus en plus élevée. Causes l'opération de recherche pour ralentir
Il y a trois idées pour continuer à optimiser : la compression du chemin, la division du chemin et la réduction de moitié du chemin
3.2.1 Compression du chemin (compression du chemin)
Faites en sorte que tous les nœuds du chemin pointent vers le nœud racine lorsque découverte, réduisant ainsi la hauteur de l'arbre
public class UniondFind_QU_S extends UnionFind{
// 创建sizes 数组记录 以元素（下标）为根结点的元素（节点）个数
private int[] sizes;
public UniondFind_QU_S(int capacity) {
super(capacity);
sizes = new int[capacity];
//初始都为 1
for(int i = 0;i < sizes.length;i++) {
sizes[i] = 1;
}
}
@Override
public int find(int v) {
rangeCheck(v);
while (v != parents[v]) {
v = parents[v];
}
return v;
}
@Override
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if(p1 == p2) return;
//如果以p1为根结点的元素个数 小于 以p2为根结点的元素个数 p1并到p2上，并且更新p2为根结点的元素个数
if(sizes[p1] < sizes[p2]) {
parents[p1] = p2;
sizes[p2] += sizes[p1];
// 反之 则p2 并到 p1 上，更新p1为根结点的元素个数
}else {
parents[p2] = p1;
sizes[p1] += sizes[p2];
}
}
}Bien que cela puisse réduire la hauteur de l'arbre, le coût de mise en œuvre est légèrement plus élevé3.2.2 Division du cheminFaites en sorte que chaque nœud du chemin pointe vers son grand-parent node public class UnionFind_QU_R extends UnionFind_QU {
// 创建rank数组 ranks[i] 代表以i为根节点的树的高度
private int[] ranks;
public UnionFind_QU_R(int capacity) {
super(capacity);
ranks = new int[capacity];
for(int i = 0;i < ranks.length;i++) {
ranks[i] = 1;
}
}
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if(p1 == p2) return;
// p1 并到 p2 上 p2为根 树的高度不变
if(ranks[p1] < ranks[p2]) {
parents[p1] = p2;
// p2 并到 p1 上 p1为根 树的高度不变
} else if(ranks[p1] > ranks[p2]) {
parents[p2] = p1;
}else {
// 高度相同 p1 并到 p2上，p2为根 树的高度+1
parents[p1] = p2;
ranks[p2] += 1;
}
}
}3.2.3 Réduire de moitié le chemin
/**
* Quick Union -基于rank的优化 -路径压缩
*
*/
public class UnionFind_QU_R_PC extends UnionFind_QU_R {
public UnionFind_QU_R_PC(int capacity) {
super(capacity);
}
@Override
public int find(int v) {
rangeCheck(v);
if(parents[v] != v) {
//递归 使得从当前v 到根节点 之间的 所有节点的 父节点都改为根节点
parents[v] = find(parents[v]);
}
return parents[v];
}
}Utiliser Quick Union + optimisation basée sur le classement + division du chemin ou réduction de moitié du chemin
Il peut être garanti que la complexité temporelle amortie de chaque opération est O(a(n)), a(n)
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!