Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Prim, Union-find, Algoritmo de Kruskal, Conjuntos Disjuntos -…
Algoritmo de Prim
Etapas do Algoritmo
-
Seleção da Aresta de Menor Peso: Em cada iteração, examina-se as arestas que conectam a árvore geradora mínima atual a vértices ainda não incluídos na árvore, selecionando a aresta de menor peso.
Atualização da Árvore: A aresta selecionada é adicionada à árvore geradora mínima, e o vértice conectado por essa aresta é agora considerado parte da árvore.
Repetição: O processo de seleção de arestas e atualização da árvore continua até que todos os vértices façam parte da árvore geradora mínima.
Usado para encontrar uma árvore geradora mínima de um grafo conexo, não direcionado e ponderado. Este algoritmo é crucial para entender como encontrar subconjuntos de arestas que formam uma árvore que inclui todos os vértices, onde o peso total das arestas na árvore é minimizado.
O algoritmo de Prim começa com um vértice arbitrário como a árvore geradora mínima inicial. A partir daí, em cada passo, ele adiciona à árvore a aresta de menor peso que conecta um vértice na árvore a um vértice fora da árvore. Este processo é repetido até que todos os vértices estejam na árvore, resultando na árvore geradora mínima para o grafo.
Union-find
Aplicações:
Detecção de ciclos em grafos: Ao adicionar arestas em um grafo, podemos usar Union-Find para verificar se a adição de uma aresta cria um ciclo, unindo os conjuntos dos vértices das arestas e verificando se ambos os vértices pertencem ao mesmo conjunto antes da união.
Construção de árvores geradoras mínimas: Algoritmos como Kruskal para encontrar a árvore geradora mínima de um grafo dependem da estrutura Union-Find para selecionar arestas sem criar ciclos.
Conjuntos disjuntos dinâmicos: Em cenários onde conjuntos precisam ser unidos ou divididos frequentemente, Union-Find oferece uma maneira eficiente de manter essas coleções.
Operações principais:
Find: Determina a qual conjunto um determinado elemento pertence. Essa operação pode incluir uma etapa de "compressão de caminho" para otimizar futuras operações de busca, atualizando os representantes dos conjuntos para que eles apontem diretamente para o representante final, reduzindo assim o tempo de busca.
Union: Une dois conjuntos disjuntos em um único conjunto. Isso geralmente é feito conectando as árvores (ou conjuntos) de dois elementos, escolhendo um dos elementos como representante do novo conjunto unido. Para otimizar essa operação, técnicas como "união por rank" ou "união por tamanho" são usadas para garantir que a árvore resultante seja o mais plana possível, minimizando o tempo necessário para futuras operações de busca.
Union-Find, também conhecido como Disjoint Set Union (DSU), é uma estrutura de dados que mantém o rastreamento de elementos divididos em um ou mais conjuntos disjuntos.
A estrutura de dados Union-Find pode ser implementada usando arrays ou estruturas de dados baseadas em árvores. A chave para a eficiência dessa estrutura está nas otimizações como compressão de caminho e união por rank, que ajudam a manter a complexidade das operações quase constante, O(a(n)), onde "a" é a inversa da função de Ackermann, uma função que cresce muito lentamente, tornando as operações praticamente constantes para todos os valores práticos de n.
Algoritmo de Kruskal
Etapas do Algoritmo
-
Inicialização da Floresta: Inicialmente, cada vértice do grafo é considerado uma árvore separada na floresta.
Seleção da Aresta: A aresta de menor peso que não forma um ciclo com as arestas já incluídas na floresta é selecionada.
Unificação das Árvores: Se a aresta selecionada conecta duas árvores diferentes na floresta, estas árvores são unidas, formando uma única árvore.
Repetição: O processo de seleção de arestas e unificação de árvores continua até que haja apenas uma árvore na floresta, que é a árvore geradora mínima do grafo.
É uma abordagem popular e eficiente para encontrar a árvore geradora mínima (AGM) de um grafo conexo, não direcionado e ponderado.
O algoritmo de Kruskal constrói a árvore geradora mínima adicionando arestas em ordem crescente de peso, garantindo que nenhuma das arestas adicionadas forme um ciclo com as arestas já incluídas. Este processo continua até que a árvore inclua todos os vértices do grafo. O algoritmo faz uso de uma estrutura de dados chamada "floresta", uma coleção de árvores, onde cada árvore na floresta representa um conjunto de vértices conectados.
Conjuntos Disjuntos
Conjuntos disjuntos, também conhecidos como conjuntos separados, são grupos de elementos onde não há elementos em comum entre os grupos. Em outras palavras, a interseção de qualquer par de conjuntos é vazia. Essa propriedade é especialmente útil na organização de elementos em grupos distintos, permitindo operações eficientes de união e busca para determinar a qual conjunto um elemento pertence.