Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvore Geradora de Custo Mínimo (MST) - Coggle Diagram
Árvore Geradora de Custo Mínimo (MST)
Definição Fundamental: A tarefa consiste em, dado um conjunto de 'n' pontos, conectá-los da forma mais barata possível, de modo que haja um caminho entre qualquer par de pontos.
Conceito Técnico: Para um grafo conectado, não direcionado e com pesos, uma MST é um subgrafo que satisfaz três condições:
É conectado.
É acíclico (ou seja, uma árvore).
Contém todos os vértices do grafo original e possui o menor peso total possível (a soma dos pesos de todas as suas arestas).
Aplicações:
Projeto de todos os tipos de redes (telecomunicações, elétricas, transporte).
Utilização em algoritmos para fins de classificação.
Construção de soluções aproximadas para problemas mais complexos.
Algoritmo de Prim
Estratégia: É um algoritmo guloso que constrói uma MST através de uma sequência de subárvores em expansão.
Funcionamento:
Começa com uma subárvore consistindo em um único vértice arbitrário.
A cada iteração, expande a árvore atual de maneira gulosa, anexando o vértice mais próximo que ainda não está na árvore.
O "vértice mais próximo" é um vértice fora da árvore conectado a um vértice dentro da árvore pela aresta de menor peso possível.
O algoritmo para quando todos os vértices foram incluídos.
Características e Complexidade:
É semelhante ao algoritmo de Dijkstra.
Pode ser usado em grafos com pesos negativos.
Sua complexidade de tempo é Θ(∣V∣2) usando uma matriz de adjacência sem heap, ou Θ((∣V∣+∣E∣)log∣V∣) usando uma lista de adjacência com heap.
Passo a Passo
Grafo Inicial: Vértices A, B, C, D, E e suas arestas com pesos. O algoritmo começa no vértice A.
Visitar A: Marcar 'A' como visitado. As arestas conectadas a 'A' são adicionadas a uma fila de prioridade (heap). As distâncias para seus vizinhos são atualizadas: D[C]=3, D[B]=10, D[D]=20.
Selecionar Aresta (A,C) com peso 3: Esta é a aresta de menor peso na fila. Marcar 'C' como visitado. Analisar os vizinhos de 'C': a distância para 'B' é atualizada para 2 (pois 2 < 10) e para 'E' é 15.
Selecionar Aresta (C,B) com peso 2: É a nova aresta de menor peso. Marcar 'B' como visitado. Analisar os vizinhos de 'B': a distância para 'D' é atualizada para 5 (pois 5 < 20).
Selecionar Aresta (B,D) com peso 5: É a nova aresta de menor peso. Marcar 'D' como visitado. Analisar os vizinhos de 'D': a distância para 'E' é atualizada para 11 (pois 11 < 15).
Selecionar Aresta (D,E) com peso 11: É a última aresta necessária. Marcar 'E' como visitado.
Resultado Final: Todos os vértices foram visitados. A MST é composta pelas arestas (A,C), (C,B), (B,D) e (D,E), com um custo total de 3 + 2 + 5 + 11 = 21.
Algoritmo de Kruskal
Estratégia: Outro algoritmo guloso. É ideal para grafos esparsos (com poucas arestas), enquanto Prim é melhor para grafos densos.
Funcionamento:
Inicialmente, cada um dos ∣V∣ vértices é considerado uma MST individual.
Uma lista de todas as arestas do grafo é criada e ordenada em ordem crescente de peso.
A cada iteração, a aresta de menor peso da lista é selecionada. Se essa aresta conectar duas árvores (subconjuntos) diferentes, ela é adicionada à MST, e as duas árvores são unidas. Se a aresta conectar vértices que já estão na mesma árvore, ela é descartada para não criar um ciclo.
O processo termina quando a MST tem ∣V∣−1 arestas.
Passo a Passo
Ordenar Arestas:
Todas as 7 arestas do grafo são ordenadas por peso: (B,C,2), (A,C,3), (B,D,5), (A,B,10), (D,E,11), (C,E,15), (A,D,20). Cada vértice (A,B,C,D,E) está em seu próprio subconjunto disjunto.
Processar (B,C) com peso 2: find(B) != find(C). A aresta é adicionada à MST. Os conjuntos de B e C são unidos.
Processar (A,C) com peso 3: find(A) != find(C). A aresta é adicionada. O conjunto de A é unido ao conjunto {B,C}.
Processar (B,D) com peso 5: find(B) != find(D). A aresta é adicionada. O conjunto de D é unido ao conjunto {A,B,C}.
Processar (A,B) com peso 10: find(A) == find(B). Aresta descartada, pois criaria um ciclo.
Processar (D,E) com peso 11: find(D) != find(E). A aresta é adicionada. O conjunto de E é unido ao conjunto {A,B,C,D}.
Resultado Final: A MST está completa com 4 arestas. As arestas restantes são ignoradas. A MST resultante é a mesma do algoritmo de Prim, com custo total 21.
Estrutura de Dados: Subconjuntos Disjuntos (Disjoint Subsets)
Finalidade: Gerencia partições de um conjunto, sendo crucial para a verificação de ciclos no algoritmo de Kruskal.
Operações Principais:
find(ds, x): Retorna o representante do conjunto ao qual o elemento x pertence.
union(ds, x, y): Une os conjuntos que contêm x e y.
Implementações e Otimizações:
4.3.1 Quick-Find:
Implementação: Usa um array onde cada posição armazena o representante do elemento.
Complexidade: find é Θ(1) , mas union é Θ(n).
Otimização: "Union by size" anexa a lista menor à maior para acelerar a operação de união.
4.3.2 Quick-Union:
Implementação: Utiliza uma árvore de ponteiros para pais, onde a raiz é o representante do conjunto.
Otimizações:
Union by size/rank (união por tamanho/altura): Conecta a árvore menor (ou mais baixa) à maior (ou mais alta) para evitar que as árvores se tornem muito profundas.
Path compression (compressão de caminho): Durante a operação find, faz com que todos os nós no caminho da busca apontem diretamente para a raiz, otimizando drasticamente buscas futuras.