Árvores Geradoras Mínimas - Resumo com Exercícios

Prévia do material em texto

Algoritmos para Árvores Geradoras Mı́nimas
Introdução
Os algoritmos apresentados são aplicáveis a grafos não direcionados e suportam
arestas de custo negativo.
Algoritmo de Kruskal
Complexidade: O(m log n)
Instruções:
1. Ordene todas as arestas do grafo em ordem crescente de peso.
2. Insira em uma lista S as arestas em ordem crescente de peso, sem formar
um ciclo.
3. Caso necessário, desenhe o grafo durante o processo.
4. Se a inserção de uma aresta formar um ciclo, passe para a próxima.
Pseudo-código:
Algorithm 1 Kruskal(G, w)
1: A← ∅
2: for cada vértice v em V (G) do
3: MAKE-SET(v)
4: end for
5: Ordenar as arestas de E por peso w em ordem crescente
6: for (u, v) em E em ordem crescente do
7: if FIND-SET(u) ̸= FIND-SET(v) then
8: A← A ∪ {(u, v)}
9: UNION(u, v)
10: end if
11: end for
12: return A
1
Algoritmo de Prim
Complexidade: O(m log n)
Instruções:
1. Escolha um vértice inicial.
2. Atribua chave = 0 e pai = NULO ao vértice inicial; para os demais: chave
= infinito, pai = NULO.
3. Crie uma fila de prioridades Q com todos os vértices e suas chaves.
4. Remova o vértice de menor chave da fila.
5. Atualize as chaves e pais dos vizinhos, se necessário.
6. Repita o processo até esvaziar a fila Q.
Pseudo-código:
Algorithm 2 Prim(G, w, r)
1: for cada vértice u em V (G) do
2: Key[u] ←∞
3: Pai[u] ← NULL
4: end for
5: Key[r] ← 0
6: Q← V (G)
7: while Q ̸= ∅ do
8: u← ExtrairMı́nimo(Q)
9: for cada v em Adj[u] do
10: if v ∈ Q e w(u, v)