Please enable JavaScript.

Coggle requires JavaScript to display documents.

M13 (Levitin) - Coggle Diagram

- - - - Um importante algoritmo "guloso" capaz de construir uma árvore geradora de custo mínimo para um dado grafo é o:
        
        Algoritmo de Prim
        
        Consiste na expansão gradativa de sub-árvores de custo mínimo através da inserção, em cada iteração, do vértice mais próximo da sub-árvore até então formada
        
        Primeiramente, um dos vértices é escolhido arbitrariamente como ponto de partida, sendo a sub-árvore base. Em seguida, a cada iteração, o algoritmo identifica os vértices que não pertencem a sub-árvore, mas são adjacentes aos vértices dela, e adiciona na sub-árvore aquele cuja aresta, ligando-o a um vértice da sub-árvore, tem o menor peso dentre as demais. Esse conjunto de vértices adjacentes é denominado "franja", enquanto os vértices nem adjacentes nem presentes na sub-árvore são chamados de "não vistos".
        
        Para realizar esse procedimento, inicialmente todos os vértices são considerados não vistos, ou seja, não possuem "pais" e sua distância para a sub-árvore é dada com um valor simbólico máximo (geralmente "infinito"). O valor da distância do vértice base, no entanto, é irrelevante. Então, a partir de um vértice de referência u* (que a princípio é o vértice base), encontram-se todos os vértices u adjacentes a ele e caso a distância de u para a sub-árvore seja maior que o peso da aresta entre u* e u, então esse peso se torna a nova distância de u* para a sub-árvore e o pai de u* é atualizado para u. Além disso, caso ocorra essa atualização, cada u é adicionado a uma fila de prioridade mínima, organizada pelos valores das distâncias a sub-árvore. O topo dessa fila, então, será o novo u*.
        
        Como a cada iteração tem-se um novo u* e inicia-se com um vértice já "visitado", o algoritmo termina após n-1 iterações, pois assim todos os n vértices do grafo terão sido visitados
        
        A eficiência depende da implementação usada
        
        Se o grafo for implementado como matriz de adjacência e a fila de prioridade como um array não ordenado (no qual o elemento mínimo é encontrado por meio de um selection sort), a eficiência temporal será em Θ(|V|^2), pois a cada |V|-1 iteração a fila de prioridade vasculha todos os |V| vértices do grafo para encontrar o mínimo
        
        Se o grafo for implementado como fila de adjacência e a fila de prioridade como uma min-heap, a eficiência temporal será em Ο(|E| log(|V|)), pois a para cada uma das |E| arestas do grafo verificadas pelo algoritmo há possivelmente uma atualização da min-heap, o que é realizado em Ο(log(|V|)), sendo |V| o total de vértices
  - - - Algoritmo de Kruskal
        
        Consiste na construção da árvore a partir da junção gradativa das arestas do grafo com menor peso, de maneira que o grafo resultante da união continue sendo uma árvore (grafo conexo acíclico)
        
        Primeiramente, o conjunto de arestas é ordenado de maneira (estritamente) não decrescente e a árvore a ser construída é definida como uma "floresta" inicialmente sem vértices. A cada iteração i do algoritmo, se a união entre a floresta construída até então e a aresta i da sequência de arestas gerar um grafo acíclico, então a floresta é atualizada para o grafo resultante dessa união. O algoritmo termina quando todas as |E| arestas tiverem sido analisadas
        
        Uma maneira de aplicar o algoritmo para facilitar a verificação de aciclicidade, é a identificação, para cada aresta analisada, das árvores montadas que contém os vértices dessa aresta. Assim, para cada aresta entre vértices u e v, o grafo será acíclico se e somente se, na floresta montada até então, a árvore que contém o vértice u for diferente da que contém o vértice v
        
        Com um algoritmo eficiente para realizar as operações de união e comparação entre conjuntos, o desempenho temporal do algoritmo de Kruskal irá depender predominantemente da ordenação do conjunto de arestas, o que com um rápido algoritmo de sorting possibilita uma eficiência geral em O(|E| log(|E|)) (sendo |E| o número de arestas)
    - - makeset(x), isto é, operação que dado um elemento x do conjunto é criado um subconjunto unitário {x}
        
        Para representar um subconjunto, utiliza-se, em geral um de seus elementos que é chamado de "representante" do conjunto. Por vezes esses elementos são mapeados para inteiros e o menor deles é usado como representante
        
        Existem duas formas principais de implementação dessa ADT:
        
        Quick find ("busca rápida"), que otimiza a eficiência da operação find(x)
        
        É implementado com o uso de uma array, para indicar os representantes de cada subconjunto, e de uma lista de linked lists que armazenam os elementos de cada subconjunto
        
        Na array, o valor da posição i é o representante do subconjunto que contém o elemento mapeado no inteiro i. Na linked list, o header contém o tamanho da lista, um ponteiro para o primeiro elemento e um ponteiro para a cauda
        
        makeset(x) inicializa a array de representantes com o valor próprio de cada índice e constrói linked lists com um elemento para cada vértice. Como cada operação é realizada em Θ(1), a eficiência temporal para n vértices é Θ(n)
        
        find(x) será em Θ(1), pois basta acessar a array e retornar o representante na posição de índice x
        
        1 more item...
        
        Quick union ("união rápida"), que otimiza a eficiência da operação union(x, y)
        
        Cada subconjunto é implementado como uma árvore enraizada no elemento representante, na qual os demais nós são descendentes dessa raiz. Além disso, tem-se uma array de ponteiros que ligam os inteiros mapeados ao seu respectivo nó em uma árvore
        
        Na árvore, cada nó possui um ponteiro para seu pai (de maneira que é possível chegar ao representante a partir de qualquer nó)
        
        makeset(x) cria árvores com um único nó, e como cada criação é executada em Θ(1), a eficiência para os n nós está em Θ(n)
        
        union(x, y) apenas anexa a raiz de uma árvore a raiz da outra, o que é feito em Θ(1)
        
        1 more item...
      - find(x), isto é, operação que retorna o subconjunto contendo x como elemento
      - union(x, y), isto é, operação que substitui o subconjunto contendo o elemento x e o subconjunto contendo o elemento y por um subconjunto único que contém os elementos tanto do primeiro quanto do segundo subconjuntos