Primeiro, vejamos duas imagens de compressão de caminho:
Os conjuntos de locações sindicais são uma estrutura de dados muito delicada e prática, usada principalmente para lidar com o problema de mesclagem de alguns conjuntos não interagidos. Alguns usos comuns incluem a conexão de subgrafos, algoritmos Kruskal para encontrar a árvore de abrangência mínima e ancestrais menos comuns (ACL).
Ao usar e procurar um conjunto, primeiro haverá um conjunto de conjuntos dinâmicos disjuntos S = {S 1, S 2, ⋯, S K}, que geralmente usa um número inteiro para representar um elemento no conjunto.
Cada conjunto pode conter um ou mais elementos, e um elemento no conjunto é selecionado como um representante. Não é importante cuidar de quais elementos estão contidos em cada conjunto e não é importante cuidar de qual elemento é selecionado como representante. O que nos preocupamos é que, para um determinado elemento, podemos encontrar rapidamente o conjunto (representação) onde esse elemento está localizado e mesclar os conjuntos onde os dois elementos estão localizados e a complexidade do tempo dessas operações é constante.
Existem três operações básicas para verificação e coleta:
FECHADAS (s): Crie um novo conjunto de pesquisa e pesquisa, que contém conjuntos de elementos únicos.
Unionset (x, y): mescla os conjuntos onde o elemento x e o elemento y estão localizados e exige que os conjuntos onde X e Y estejam localizados não se cruzem e, se eles se cruzam, não se fundem.
Encontre (x): encontre o representante do conjunto onde o elemento X está localizado. Esta operação também pode ser usada para determinar se dois elementos estão no mesmo conjunto. Basta comparar seus respectivos representantes.
pacote com.datastructure.union_find; // Nossa quinta edição Union-Findpublic Class Unionfind5 {// Rank [i] representa o número de camadas da árvore representada por um conjunto enraizado por I // em Código subsequente, não devemos manter os semânticos que se deve a ranking. profundidade. É apenas um padrão para comparação private int [] classificação; private int [] pai; // pai [i] representa o nó pai apontado pela contagem privada de I -th Element Private; // número de dados // construtor public UnionFind5 (int conting) {rank = new int [count]; pai = new int [count]; this.count = count; // inicialização, cada pai [i] aponta para si mesmo, indicando que cada elemento forma seu próprio conjunto para (int i = 0; i <contagem; i ++) {parent [i] = i; classificação [i] = 1; }} // Processo de pesquisa, encontre o número do conjunto correspondente à complexidade do elemento p // O (h), h é a altura da árvore privada int find (int p) {assert (p> = 0 && p <contagem); // Compressão do caminho 1 while (p! = pai [p]) {pai [p] = pai [pai [p]]; p = pai [P]; } retornar p; // Compressão do caminho 2, algoritmo recursivo // if (p! = pai [p]) // pai [p] = find (pai [p]); // retorna pai [p]; } // Verifique se o elemento P e o elemento q pertencem a uma complexidade definida // O (h), h é a altura da árvore pública booleana isconectada (int p, int q) {return find (p) == find (q); } // Mesclar o conjunto para o qual o elemento P e o elemento q pertence // o (h) complexidade, h é a altura da árvore pública vazia UnioNelements (int p, int q) {int proot = find (p); int qroot = find (q); if (prot == qroot) retornar; // julga a direção de mesclagem com base no número diferente de elementos na árvore, onde os dois elementos estão localizados // mescla um conjunto com menos elementos em um conjunto com mais elementos se (classificação [prot] <rank [qroot]) {parent [proto] = Qroot; } else if (rank [qroot] <rank [prot]) {parent [qroot] = proto; } else {// rank [proto] == classificação [qroot] pai [proto] = qroot; classificação [qroot] += 1; // No momento, mantenho o valor da classificação}}}Resumir
O exposto acima é toda a explicação detalhada do código de compactação do caminho neste artigo sobre a implementação e coleta de programação Java. Espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!