Aula 03 - Union Find¶

Referências úteis¶

https://algs4.cs.princeton.edu/15uf/ - capítulo do algs4 sobre union find

Conjuntos disjuntos¶

Seja S = {$S_1, S_2, …, S_n$} uma coleção de conjuntos disjuntos ou seja $S_i \cap S_j = \empty $ , para todo i e j
Coleção disjunta dinâmica : Conjuntos são modificados ao longo do tempo
- Ex : grafo dinâmico.
  - Inicialmente, cada item do grafo está disjunto, é um conjunto disjunto
  - Posteriormente, posso montar arestas entre os itens e conectá-los, e monto um componente (chamamos assim no caso de grafo)/conjunto.
Quero montar uma API com operações que acrescenta arestas, encontra ligações…

public Class (QuickFind/QuickUnionr)UF { //quick find e quick union são implementações diferentes pra essa classe
    private int[] pai;
    private int[] sz;
    private int count;
    public _ UF (int n) {
        count = n;
        pai = new int[n];
        sz = new int[n];
        for (int i = 0; i < n; i++) {
            id[i]  = i;
            sz[i] = 1;
            
        }
    }
    
    public int count() {
        return count;
    }
    
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
    
    public int find(int p) {
        while(p != pai[p]) 
            	pai[p] = pai[pai[p]];
            	p = pai;
            
        }
       return p;
    }
    
    public void union (int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if (pID == qID)
            	return;
        if (sz[pID] < sz[qID]) {
            pai[pID] = qID;
            sz[qID] += sz[pId];
        }
        else {
            pai[qID] = pID;
            sz[pID] += sz[qID]; 
        }
        pai[pID] = qID;
        count--;
    }
}

Invariante¶

Toda árvore de altura h tem pelo menos $2^h$ elementos portanto, $lg(n) >= h$.

Análise de tempo¶

1a linha : implementação com o vetor de IDs (qual o ID do conjunto que o elemento está)

2a linha : agora os caras são organizados pelo pai, o que faz demorar mais o find e o union fica mais demorado porque depende de find - implementação usando florestas disjuntas

3a linha: vamos juntar o menor grupo ao maior : union by size. Dessa forma eu minimizo o custo do find nas operções de find.

UF(n)	union	find
$O(n)$	$O(n)$	$O(1)$
$O(n)$	$O(n)$	$O(n)$
$O(n)$	$O(lg(n)) $	$O(lg(n))$

Pior caso do weighted quick union¶

Quando usamos o QuickUnion normal, a altura do grafo pode aumentar a cada operação de union
Mas usando o weighted quickUnion, a altura só aumenta quando voce dobra o número de caras

Path Compression UF¶

Ideia : encurtar os caminhos durante cada find()
- A cada vez que eu rodo o find e procuro quem é o pai de uma arvore, eu aproveito e pego todos os filhos e ligo diretamente ao pai

public int find (int p) {
    if (p != pai[p])
        pai[p] = find(pai[p]);
    return pai[p];  
    }
}

Consumo de tempo amortizado (union c/ path compression find) :¶

$$ O(lg^*n) $$

Uma função log-estrela é definida como :
- Uma função lg-estrela é o menor k tal que $$ lg(lg(lg(…(n)))) <= 1 $$
- Ex : $$ lg(8) = 3, lg(3) \approx 1 \therefore lg^*8 = 2 $$