Algoritmo de Kruskal
Disciplina Análise de Algoritmos
Bacharelado em CC
Algoritmo de Kruskal
Utiliza o arcabouço geral do método guloso para MST, com os
seguintes detalhes:
• O conjunto inicial X0 é um subgrafo com |V| vértices isolados e
nenhuma aresta.
• A cada etapa k :
– O corte (S,V-S) só deve satisfazer a propriedade de “respeitar” o
Xk-1, isto é, cada aresta de Xk-1 tem seus dois vértices do mesmo
lado do corte. Nenhuma aresta de Xk-1 atravessa o corte.
– Não necessariamente um lado do corte contém TODAS as
arestas de Xk-1, como no algoritmo PRIM.
Exemplo de Aplicação de Kruskal
Considere o seguinte grafo G
Etapa 0 : X0 é o subgrafo X0 = (V,E) onde V = {a,b,c,d,e,f,g,h,i} e E = 
Lembre que : No algoritmo de PRIM, na etapa 0, X0 = (V,E), onde V = , E = 
Etapa 1
Considera a aresta de menor custo {h,g} ligando duas
componentes conexas h e g distintas !
X1 = {h-g}
Etapa 2
X1 = {h-g}
Considera a 2a aresta de menor custo {i,c} – ligando
duas componentes conexas distintas i e c
X2 = {h-g,i-c}
Etapa 3
X2 = {h-g,i-c}
Considera a 3a aresta de menor custo {g,f} – ligando
duas componentes conexas distintas {h-g} e {f}
X3 = {h-g,i-c,g-f}
Etapa 4
X3 = {h-g,i-c,g-f}
Considera a 4a aresta de menor custo {a,b}, ligando as
componentes conexas distintas {a} e {b}
X4 = {h-g,i-c,g-f,a-b}
Etapa 5
X4 = {h-g,i-c,g-f,a-b}
Considera a 5a aresta de menor custo {c,f}, ligando duas
componentes conexas distintas
X5 = {h-g,i-c,g-f,a-b,c-f}
Etapa 6
X5 = {h-g,i-c,g-f,a-b,c-f}
Considera a 6a aresta de menor custo {c,d} ligando duas
componentes conexas distintas.
Repare que a aresta i-g liga vértices da mesma componente
conexa de X6, logo não pode ser considerada, embora seja
de menor custo !
Resultado final
Exercicio: continue as demais etapas a partir da sétima até chegar
neste resultado final.
Justificando a corretude do
Algoritmo de Kruskal
Considere o seguinte grafo G
Etapa 0 : X0 é o subgrafo X0 = (V,E) onde V = {a,b,c,d,e,f,g,h,i} e E = 
Corte S = { } , V – S = V
Lembre que : No algoritmo de PRIM, na etapa 0, X0 = (V,E), onde V = , E = 
Etapa 1
Considera a aresta de menor custo {h,g}
Corte: S = {h}, V- S = {a,b,c,d,e,f,g,i}
S contém os vértices das arestas de X0
(nenhum vértice !)
X1 = {h-g}
Etapa 2
X1 = {h-g}
Considera a 2a aresta de menor custo {i,c}
Corte: S = {h,g,i}, S contém os vértices das arestas de X1
X2 = {h-g,i-c}
Etapa 3
X2 = {h-g,i-c}
Considera a 3a aresta de menor custo {g,f}
Corte: S = {h,g} V- S = {i,c,d,e,f,a,b}, cada aresta de X2
está contida em S ou em V-S.
X3 = {h-g,i-c,g-f}
Etapa 4
X3 = {h-g,i-c,g-f}
Considera a 4a aresta de menor custo {a,b}
Corte: S = {h,g,f,a} V- S = {i,c,d,e,b}, cada aresta de X3 está
contida em S ou em V-S.
X4 = {h-g,i-c,g-f,a-b}
Etapa 5
X4 = {h-g,i-c,g-f,a-b}
Considera a 5a aresta de menor custo {c,f}
Corte: S = {h,g,f,a,b}, V- S = {i,c,d,e}
X5 = {h-g,i-c,g-f,a-b,c-f}
Etapa 6
X5 = {h-g,i-c,g-f,a-b,c-f}
Considera a 6a aresta de menor custo {c,d}
Corte: S = {h,g,i,c,a,b,f}, V-S = {d,e}
X6 = {h-g,i-c,g-f,a-b,c-f,c-d}
Repare que a aresta i-g liga vértices da mesma componente
conexa de X6, logo não pode ser considerada, embora seja de
menor custo !
Algoritmo de Kruskal
1. X = grafo (V,)
2. Para cada vértice v ∈ V
3. Makeset(v) ; % transforma cada vértice isolado é
uma componente conexa de X
4. Ordena as arestas de G em ordem crescente de custo
5. Para cada aresta (u,v) de G, considerando a ordem
crescente de custo
6. Se Find(u)  Find(v) % no máximo |V| - 1 vezes
7. X = X  {(u,v)}
8. Union(Find(u), Find(v)
9. Retorna X
Esquema Geral:
|V|.makeset + O(|E|.log(|E|) + |E|.(Find) + (|V| - 1) (Union)
Análise da Complexidade
Esquema Geral:
|V|.makeset + O(|E|.log(|E|) + |E|.(Find) + (|V| - 1) (Union)
A complexidade depende da implementação das operações de
conjunto:
Makeset, Find, Union
Implementação de Find e Union utilizando representação de
conjuntos por árvores e ranks em cada nó da árvore : log(|V|)
Complexidade = |V|.O(1)+ O(|E|.log(|E|) + O(|E|+|V|).(log(|V|))
Pior caso |E| = |V|2 : O( log(|E|) = O( log(|V) )
Complexidade = O( |V|2 log(|V| )
Ver prova nos slides
seguintes
Representação de conjuntos como
àrvores
Como representar um conjunto {A1,..., An} por uma árvore ?
Exemplo: {A,B,C,D,E,F,G}
Passo 0: Constrói, para cada elemento X, uma árvore de um único elemento
(raiz) X0 de rank 0.
A0
B0
C0
D0
E0
F0
G0
Passos 1, 2 e 3: union(A,B), union(C,D), union(E,F), resultando em 4 árvores:
B1
D1
F1
A0
C0
E0
union(A,B)
union(C,D)
union(E,F)
G0
• Passos 4 e 5: union(B,D), union(F,G) : resultado 2 árvores
D2
F1
B1
E0
C0
G0
A0
union(B,D)
union(F,G)
Passo 6 : union(D,F)
D2
B1
C0
F1
A0
E0
Representação de {A,B,C,D,E,F,G} em árvore
G0
Representantes de Conjuntos
• O representante oficial de uma árvore é a sua raiz.
• Assim, a árvore
D2
B1
C0
A0
tem como representante oficial a raiz D.
Também pode-se se referir a esta árvore através de qualquer de seus nós. Por
exemplo, a árvore da figura pode ser referida por “A”. Mas seu representante
oficial é D.
Operação Find(A): retorna o representante oficial da árvore contendo o nó A = D
Se rank D é k então Find(A) executa no máximo k passos para chegar até a raiz D.
Operações Find e Makeset
Makeset(x)
1.
pai(x) = x
2.
rank(x) = 0
Complexidade de Makeset = O(1)
Find(x)
1.
While x  pai(x)
2.
x = pai(x)
3.
Retorna x
Complexidade de Find(x) = O(k), onde k = profundidade da árvore contendo x
= rank da raiz desta árvore
Observação: a raiz de uma árvore é o único nó que é seu próprio pai.
Operação Union
Union(x,y)
1.
2.
3.
4.
5.
6.
7.
8.
9.
Rx = Find(x)
Ry = Find(y)
Se Rx = Ry: retorna x
Se rank(Rx) > rank(Ry)
pai(Ry) = Rx
Else
Pai(Rx) = Ry
Se rank(Rx) = rank(Ry)
rank(Ry) = Rank(Ry) + 1
Complexidade das operações Find
e Union
Qual a relação entre o número n de elementos de uma árvore e a sua
profundidade k ?
Vamos mostrar k ≤ log2(n)
Propriedade 1: Para todo x (diferente da raiz), rank(x) < rank(pai(x))
Propriedade 2: Qualquer nó de rank k tem no mínimo 2k descendentes.
Prova: por indução sobre k
Base da indução: k = 0. Neste caso o único descendente é o próprio nó. Portanto
número de descendentes = 1 = 20
Passo da indução: Suponha o resultado verdadeiro para rank = k-1 e seja x um
nó de rank k > 0. Neste caso, a árvore de x foi obtida juntando-se duas árvores
de raiz u e raiz v de mesmo rank k-1. Logo o número de descendentes de x =
número de descendentes de u + número de descendentes de v ≤ 2k-1 + 2k-1 = 2.
2k-1 = 2k
Complexidade das operações Find
e Union
Qual a relação entre o número n de elementos de uma árvore e a sua
profundidade k ?
Considere uma árvore de n elementos com raiz x de rank k
Então k = profundidade da árvore
Pela propriedade 2, temos que n ≥ 2k
Logo: log2(n) ≥ k
Portanto : k ≤ log2(n)
Portanto a complexidade de Find e Union é O(log(n)), uma vez que todas as
árvores têm profundidade máxima log2(n)