Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores geradora de peso mínimo - Coggle Diagram
Árvores geradora de peso mínimo
Algorítimo de Kruskal
Ordenar de maneira não decrescente as arestas pelos seus pesos
Procurar nessa lista ordenada e adicionar a próxima aresta se ela não formar um ciclo caso contrário simplesmente pula essa aresta
Floresta inicial com V vértices
Em cada iteração o algorítimo encontra a próxima aresta e os vértices que são conectados por essa aresta é criada uma árvore maior que contenha os dois vértices
Com um método eficiente de ordenação O(|E|log|E|)
Union-Find
Depois de ser inicializado como uma coleção de n subconjuntos de um elemento diferente de S, o conjunto é submetida a uma sequência de operações de unir e encontrar elementos
Um novo ADT
Criar(x)
Cria um conjunto com 1 elemento
Encontrar(x)
Retorna o subconjunto que contém X
Unir(x,y)
Constrói a união dos subconjuntos que contém X com Y
Quick Find
Otimiza operação de encontrar
Array em que os os valores indicam os subconjuntos que contêm aqueles elementos
Cada subconjunto é implementado como uma lista encadeada em que o header contém um ponteiro para o primeiro e ultimo elemento da lista junto com o número de elementos
na lista
Para melhorar a eficiência temporal em uma operação de unir anexar a menor lista na maior (Unir pelo tamanho)
Eficiência temporal
Encontrar Θ(1)
Sequência de unir Θ(n²) sem unir pelo tamanho
Sequência de unir O(n log n) no pior caso usando unir pelo tamanho
Criar Θ(n)
Sequência de no máximo n - 1
unir e m encontrar está em O (n log n + m)
Quick Union
Otimiza operação de unir
Cada subconjunto por uma árvore com uma raiz. Os nós da árvore contêm os elementos do subconjunto (um por nó), com o elemento da raiz considerado o representante do subconjunto; as arestas da árvore são direcionadas dos filhos para seus pais
Deixar mais eficiente o encontrar é conectar a menor árvore na maior (unir pelo tamanho)
Eficiência temporal
Unir Θ(1)
Encontrar O(n)
Criar Θ(n)
Encontrar O(log n) com unir pelo tamanho
Sequência de no máximo n - 1 unir
e m encontrar está em O (n + m log n)
Maneira de menor custo de conectar um conjunto de vértices
Árvore geradora de um grafo sem direções e todo conectado é seu grafo conectado e acíclico
Árvore geradora mínima é quando o grafo tem pesos associados às arestas e o peso da árvore(soma de todos os pesos das arestas) é minimo
Algorítimo de Prim
Algorítimo constrói a árvore geradora mínima através de uma sequência de expansão de sub-árvores
Começa com uma sub-árvore com apenas um vértice V arbitrário
Em cada iteração o algorítimo expande a sub-árvore associando o vértice que não está na sub-árvore conectado a outro vértice na árvore com a aresta com menor peso
Para encontrar o próximo vértice adicionar nos vértices dois rótulos: qual o vértice com menor peso e seu peso
Ou separar os vértices que não estão na árvore entre os que podem ser acessados (fringe) e os que não (unseen)
Ao encontrar o próximo vértice U
Mover U do conjunto de vértices fora da árvore para o conjunto de dentro da árvore
atualizar o peso dos vértices que são adjacentes a U
Os vértices que não são adjacentes a nenhum vértice da árvore recebem no rótulo infinito
Eficiência temporal
Se o grafo é representado por uma matriz com os pesos e a fila com prioridade estiver implementada em um array desordenado
Θ(|V|²)
Se a fila com prioridade estiver implementada como uma min-heap
O(|E|log|V|)