Aula 21 - Árvores Geradoras de Custo Mínimo: Algoritmo de Kruskal e Estrutura Union-Find
Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica
Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado e André Grahl.
Entrada: Um grafo não direcionado G=(V,E) e um custo c_e para cada aresta e\in E.
Saída: Uma árvore T=(V,E'), com E'\subseteq E, de custo mínimo (soma dos custos das arestas em E') que alcança todos os vértices.
Abordagem Gulosa: Constrói a solução passo a passo aplicando decisões locais que otimizam algum critério.
P. Qual decisão?
Propriedade do Corte. Considere uma aresta e de G. Suponha que existe um corte(A,B) tal que e é a aresta de menor custo de G que o corta. Então e pertence à árvore geradora mínima de G.
Usando listas/vetores: O(mn)
Union-Find: O(m\log{}n).
Ordem: A–B (1), C–A (1), C–D (2), D–A (2), E–G (2), C–F (3), D–B (3), D–F (4), E–B (4), D–E (5), D–G (5), F–G (6).
| # | aresta | decisão | componentes | |\textcolor{#3a7a10}{T}| | W(\textcolor{#3a7a10}{T}) |
|---|---|---|---|---|---|
| 1 | A–B (1) | aceita | \{A,B\}\;\{C\}\;\{D\}\;\{E\}\;\{F\}\;\{G\} | 1 | 1 |
| 2 | C–A (1) | aceita | \{A,B,C\}\;\{D\}\;\{E\}\;\{F\}\;\{G\} | 2 | 2 |
| 3 | C–D (2) | aceita | \{A,B,C,D\}\;\{E\}\;\{F\}\;\{G\} | 3 | 4 |
| 4 | D–A (2) | rejeita (ciclo) | \{A,B,C,D\}\;\{E\}\;\{F\}\;\{G\} | 3 | 4 |
| 5 | E–G (2) | aceita | \{A,B,C,D\}\;\{E,G\}\;\{F\} | 4 | 6 |
| 6 | C–F (3) | aceita | \{A,B,C,D,F\}\;\{E,G\} | 5 | 9 |
| 7 | D–B (3) | rejeita (ciclo) | \{A,B,C,D,F\}\;\{E,G\} | 5 | 9 |
| 8 | D–F (4) | rejeita (ciclo) | \{A,B,C,D,F\}\;\{E,G\} | 5 | 9 |
| 9 | E–B (4) | aceita | \{A,B,C,D,E,F,G\} | 6 | 13 |
Invariante do algoritmo. Em cada passo, o conjunto T construído por Kruskal é um subconjunto de alguma Árvore Geradora Mínima.
Justificativa com a propriedade do corte.
Conclusão.
No Kruskal: para cada aresta e=(u,v), precisamos saber se \textcolor{#3a7a10}{T}\cup\{e\} tem ciclo.
Observação. \textcolor{#3a7a10}{T} é sempre uma floresta. Então
T\cup\{(u,v)\} tem ciclo \iff u e v já estão na mesma componente de T.
Basta manter a partição de V nas componentes de T e saber:
| Operação | O que faz | No Kruskal |
|---|---|---|
Inicialize(V) |
cria n conjuntos unitários \{v\} | T=\emptyset: cada vértice isolado |
Find(v) |
devolve o representante do conjunto de v | ciclo \iff Find(u) = Find(v) |
Union(u,v) |
une os conjuntos de u e de v | aceitar (u,v) funde duas componentes |
Ideia: cada conjunto é uma árvore enraizada em que cada elemento aponta para o seu pai. A raiz é o representante do conjunto.
pai[1..n].pai[v] = v \iff v é raiz (representante).pai a partir de v, chegamos ao representante do conjunto de v.Atenção: as árvores da Union-Find não são as árvores de \textcolor{#3a7a10}{T}: elas só registram quem está junto com quem.
Find e Union (Versão Simples)Custo: Find e Union custam O(\text{altura da árvore}).
P. Qual pode ser a altura de uma árvore?
A versão simples não controla a altura. Considere a sequência
\texttt{Union}(1,2),\ \texttt{Union}(1,3),\ \texttt{Union}(1,4),\ \dots,\ \texttt{Union}(1,n).
Union(1,k) executa Find(1), que percorre k-1 ponteiros: total \Theta(n^2).Find pode custar \Theta(n) \Rightarrow laço do Kruskal em O(mn), igual a usar listas.Ideia: ao unir, pendurar a árvore mais baixa na mais alta.
Cada raiz r guarda \texttt{rank[r]}, a altura da sua árvore (inicialmente 0).
Antes de Union(3,6)
Depois
Lema. Com união por rank, uma árvore cuja raiz tem rank k tem altura k e pelo menos 2^k nós.
Prova. Indução no número de operações Union.
Inicialize, cada árvore tem rank 0, altura 0 e 1 = 2^0 nó.Corolário. 2^k \le n \Rightarrow k \le \log_2 n. Toda árvore tem altura \le \log_2 n, então
FindeUnioncustam O(\log n).
No Kruskal: 2m Find + (n-1) Union = O(m \log n), mesmo custo da ordenação.
Ideia: o Find já percorre o caminho até a raiz; aproveitamos para fazer todos os nós visitados apontarem diretamente para ela.
Antes de Find(8)
Depois
Find a partir de 9 também ficam mais curtos.rank: ele passa a ser apenas um limitante superior da altura, e o Lema continua valendo.Arestas, na ordem: (1,2),\ (3,4),\ (2,3),\ (5,6),\ (1,4),\ (4,5). Union por rank (empate: a raiz de u vence) + compressão de caminho.
| # | aresta | raízes | decisão | mudança |
|---|---|---|---|---|
| 1 | (1,2) | 1,\ 2 | une | \texttt{pai[2]}\gets 1,\ \texttt{rank[1]}\gets 1 |
| 2 | (3,4) | 3,\ 4 | une | \texttt{pai[4]}\gets 3,\ \texttt{rank[3]}\gets 1 |
| 3 | (2,3) | 1,\ 3 | une | \texttt{pai[3]}\gets 1,\ \texttt{rank[1]}\gets 2 |
| 4 | (5,6) | 5,\ 6 | une | \texttt{pai[6]}\gets 5,\ \texttt{rank[5]}\gets 1 |
| 5 | (1,4) | 1,\ 1 | rejeita (ciclo) | \text{compressão: }\texttt{pai[4]}\gets 1 |
| 6 | (4,5) | 1,\ 5 | une | \texttt{pai[5]}\gets 1\ \ (\text{rank } 2 > 1) |
| Estratégia | Custo por operação | Laço do Kruskal |
|---|---|---|
| versão simples | O(n) | O(mn) |
| união por rank | O(\log n) | O(m\log n) |
| união por rank + compressão | O(\alpha(n)) amortizado | O(m\,\alpha(n)) |
Teorema (Tarjan, 1975). Com as duas heurísticas, qualquer sequência de q operações sobre n elementos custa O(q\,\alpha(n)).
Find isolado ainda pode ser caro, mas o custo médio ao longo da sequência é O(\alpha(n)).Visualização interativa: visualgo.net/en/ufds
A_0(j) = j+1, \quad A_k(j) = A_{k-1}^{(j+1)}(j) (A_{k-1} aplicada j+1 vezes), \quad \alpha(n) = \min\{k : A_k(1) \ge n\}.
A_0(1) = 2,\quad A_1(1) = 3,\quad A_2(1) = 7,\quad A_3(1) = 2047,\quad A_4(1) \gg 10^{80}.
O próximo degrau, \alpha(n) = 5, só ocorre para n > 10^{80}: na prática, \alpha(n) \le 4.
Entrada: grafo G=(V,E) com custo c_e para cada e\in E.
Saída: árvore geradora mínima T.
| Etapa | Custo | Justificativa |
|---|---|---|
| ordenar as arestas | O(m\log m) | ordenação por custo |
| inicializar Union-Find | O(n) | um conjunto por vértice |
| percorrer as arestas | O(m) | uma passada por E |
| operações Union-Find | O(m\alpha(n)) | O(\alpha(n)) amortizado por operação |
No laço, há no máximo 2m chamadas de Find e no máximo n-1 chamadas de Union. T(n,m) = O(m\log m) + O(n) + O(m\alpha(n)).
Como \alpha(n) cresce extremamente devagar, o gargalo é a ordenação. Em grafo simples, m \leq n^2, logo \log m \leq 2\log n.
\boxed{T(n,m)=O(m\log m)=O(m\log n)}
\text{Se as arestas já estão ordenadas: } O(m\alpha(n)+n).
Ver também: arvore_geradora_minima.ipynb
| Ano | Algoritmo | Complexidade |
|---|---|---|
| 1975 | Yao | O(m\log\log n) |
| 1976 | Cheriton-Tarjan | O(m\log\log n) |
| 1984 | Fredman-Tarjan | O(m\log^{*} n) |
| 1997 | Chazelle | O(m\alpha(n)\log\alpha(n)) |
| 2000 | Chazelle | O(m\alpha(n)) |
| 2002 | Pettie-Ramachandran | Ótimo |
| ? | ? | O(m) |
Observação: O(m) algoritmo randomizado por Karger-Klein-Tarjan (1995).
?