Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de MST (Árvore Geradora Mínima) - Coggle Diagram
Algoritmos de MST (Árvore Geradora Mínima)
Definição
Conjunto de arestas que conecta todos os vértices de um grafo conexo e ponderado.
Sem ciclos.Custo total mínimo (soma dos pesos das arestas).
Algoritmo de Prim
Ideia principal: Cresce a árvore adicionando a aresta de menor peso que conecta um vértice visitado a um não visitado.
Estrutura de dados comum: Min-heap (fila de prioridade).
Início: Escolhe um vértice qualquer.
Etapas:
Começa com um vértice.
Adiciona a menor aresta que conecta com um novo vértice.
Repete até visitar todos os vértices.
Complexidade:
Com heap: O(E log V)
Sem heap: O(V²)
Algoritmo de Kruskal
Ordena todas as arestas por peso e adiciona as menores evitando ciclos.
Etapas:
Ordena as arestas por peso.
Para cada aresta, verifica se conecta dois componentes diferentes.
Se não forma ciclo, adiciona à MST.
Repete até ter V-1 arestas.
Complexidade: O(E log E)
Union-Find
Manter o controle de um conjunto de elementos particionado em subconjuntos disjuntos, permitindo:
Verificar se dois elementos pertencem ao mesmo conjunto.
Unir dois conjuntos diferentes.
Find() – Encontrar o representante (ou raiz)
Union(x, y) – Unir os conjuntos que contêm x e y