Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmos de Prim, Kruskal e Operações com Conjuntos - Coggle Diagram

- - - - Minimum Spanning Tree Problem (MST): uma spanning tree de um grafo conectado não dirigido é o seu subgrafo acíclico conectado que contém todos os vértices do grafo. A MST é a spanning tree de menor peso (a soma do peso de todas as arestas). O problema de MST é achar a menor spanning tree para um dado grafo conectado com peso.
        
        O número de spanning trees cresce exponencialmente com o tamanho do grafo.
        
        Não é fácil gerar todas as spanning trees para um dado grafo.
        
        O algoritmo de Prim gera a MST através de uma sequência de árvores em expansão:
        
        A árvore inicial consiste em um único vértice selecionado arbitrariamente;
        
        Em cada iteração, o algoritmo expande a árvore anexando a ela o vértice mais próximo (e que não está na árvore);
        
        1 more item...
- - - - Ordena as arestas do grafo em ordem não crescente em relação aos seus pesos.
        
        Começando com um subgrafo vazio, percorre a lista ordenada, adicionando a próxima aresta da lista ao subgrafo atual, se a inclusão não for criar um ciclo.
        
        Um novo ciclo é criado se e somente se a nova aresta conecta dois vértices já conectados por um caminho.
        
        Podemos considerar as operações do algoritmo como uma progressão por uma série de florestas contendo todos os vértices de um grafo e algumas de suas arestas.
        
        A floresta inicial possui |V| árvores triviais, cada uma com um único vértice do grafo;
        
        A floresta final contém apenas uma árvore;
        
        Em cada iteração, o algoritmo seleciona a próxima aresta (u, v) e procura as árvores que contém os vértices u e v. Se elas não forem as mesmas, une-as para formar uma árvore maior, adicionando a aresta (u, v).
        
        A eficiência de Kruskal se encontra em big-oh(|E|log|E|).
- - - - A maioria das implementações dessa ADT requerem um elemento representante de cada subconjunto. Algumas implementações selecionam arbitrariamente enquanto outras impõem alguns critérios para o representante, como ser o menor elemento, por exemplo.
        
        Podemos implementar utilizando duas maneiras:
        
        Quick Find
        
        Otimiza o tempo de eficiência da operação find(x).
        
        Usa um array indexado pelos elementos do conjunto subjacente S. Os valores do array indicam os representantes dos subconjuntos contendo os elementos. Cada subconjunto é implementado como uma linked list, na qual o header contém ponteiros para o primeiro e último elementos da lista, junto ao número de elementos na lista.
        
        Makeset(x): relaciona o elemento correspondente no array representante para x e inicializa a linked list correspondente para um único nó com o valor x. Eficiência temporal está em big-theta(1).
        
        1 more item...
        
        Quick Union
        
        Representa cada subconjunto por uma árvore enraizada. Os nós da árvore contém os elementos do subconjunto (um elemento por nó). A raiz é o representante.
        
        Makeset(x) está em big-theta(1).
        
        Union(x, y): anexa a raiz da árvore de y à raiz da árvore de x, deletando a árvore de y da coleção. Eficiência: big-theta(1).
        
        1 more item...