Tout d'abord, regardons deux images de compression de chemin:
Union-Find SETS est une structure de données très délicate et pratique, qui est principalement utilisée pour faire face au problème de fusion de certains ensembles non inférieurs. Certaines utilisations courantes comprennent la connexion des sous-graphiques, les algorithmes de Kruskal pour trouver l'arbre couvrant minimum et les ancêtres les moins courants (LCA).
Lors de l'utilisation et de la recherche d'un ensemble, il y aura d'abord un ensemble d'ensembles dynamiques disjoints s = {s 1, s 2, ⋯, s k}, qui utilise généralement un entier pour représenter un élément dans l'ensemble.
Chaque ensemble peut contenir un ou plusieurs éléments, et un élément de l'ensemble est sélectionné en tant que représentant. Il n'est pas important de se soucier des éléments contenus dans chaque ensemble, et il n'est pas important de se soucier de l'élément sélectionné comme représentant. Ce qui nous intéresse, c'est que pour un élément donné, nous pouvons rapidement trouver l'ensemble (représentation) où se trouve cet élément, et fusionner les ensembles où se trouvent les deux éléments, et la complexité temporelle de ces opérations est constante.
Il existe trois opérations de base pour la vérification et la collecte:
MakeSet (s): Créez un nouveau jeu de recherche, qui contient S des ensembles à éléments uniques.
Unionset (x, y): fusionne les ensembles où se trouve l'élément x et l'élément y, et nécessite que les ensembles où X et Y se trouvent ne se croisent pas, et s'ils se croisent, ils ne fusionnent pas.
Trouver (x): Trouvez le représentant de l'ensemble où se trouve l'élément x. Cette opération peut également être utilisée pour déterminer si deux éléments se trouvent dans le même ensemble. Comparez simplement leurs représentants respectifs.
package com.datastructure.union_find; // notre cinquième édition syndicat-fidpublic class UnionFind5 {// Rank [i] représente le nombre de couches de l'arbre représenté par un ensemble enraciné par i // dans le code ultérieur, nous ne conserverons pas le sémantique de rang, c'est-à-dire que la valeur du rang ne peut pas être la valeur de la couche de l'arbre pendant la compression de traject profondeur. Ce n'est qu'une norme pour la comparaison privée int []; Int privé [] parent; // parent [i] représente le nœud parent pointé par le i-tth élément privé int count; // Nombre de données // Constructeur public UnionFind5 (int count) {Rank = new int [count]; parent = new int [count]; this.count = count; // L'initialisation, chaque parent [i] pointe vers lui-même, indiquant que chaque élément forme son propre ensemble pour (int i = 0; i <count; i ++) {parent [i] = i; rang [i] = 1; }} // Processus de recherche, recherchez le numéro de jeu correspondant à l'élément p // o (h) complexité, h est la hauteur de l'arborescence private int find (int p) {assert (p> = 0 && p <count); // Path Compression 1 while (p! = parent [p]) {parent [p] = parent [parent [p]]; p = parent [p]; } return p; // Path Compression 2, Algorithme récursif // if (p! = parent [p]) // parent [p] = find (parent [p]); // return parent [p]; } // Vérifiez si l'élément P et l'élément Q appartiennent à un ensemble // o (h) complexité, H est la hauteur de l'arbre public booléen isConned (int p, int q) {return find (p) == find (q); } // fusionner l'ensemble auquel l'élément p et l'élément q appartient // o (h) complexité, h est la hauteur de l'arbre public public syndionElements (int p, int q) {int proot = find (p); int qroot = trouver (q); if (proot == qroot) return; // juge la direction de fusion en fonction du nombre différent d'éléments dans l'arbre où les deux éléments sont situés // fusionnent un ensemble avec moins d'éléments sur un ensemble avec plus d'éléments si (rang [proot] <rang [qroot]) {parent [proot] = qroot; } else if (rank [qroot] <rank [proot]) {parent [qroot] = proot; } else {// Rank [proot] == Rank [qroot] parent [proot] = qroot; rang [qroot] + = 1; // Pour le moment, je maintiens la valeur du rang}}}Résumer
Ce qui précède est toute l'explication détaillée du code de compression de chemin dans cet article sur la mise en œuvre et la collecte de la programmation Java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!