Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 14 - Coggle Diagram

- - - - Definição: o subgrafo acíclico de um grafo sem direção conectado. Se o grafo tem peso nas arestas, a árvore de extensão mínima tem o menor peso possível.
        
        O problema de árvore de extensão mínima é o problema de encontrar a árvore de extensão mínima de um dado grafo conexo com peso.
      - Se tentarmos construir por busca à exaustão, tem dois obstáculos.
        
        O número de árvores de extensão cresce exponencialmente com o tamanho do grafo (densos)
        
        Gerar todas árvores de extensão é mais difícil que achar a mínima.
      - Algoritmo de Prim
        
        Algoritmo que constrói a árvore de extensão mínima por meio de uma sequência de sub-árvores, que expande.
        
        A sub-árvore inicial consiste de uma vértice arbitrária do conjunto de vértices do grafo.
        
        Em cada iteração, a árvore expande de maneira GREEDY, se conectando com a vértice mais próxima fora da árvore.
        
        O algoritmo termina após todas as vértices do grafo serem incluídas na árvore sendo construída. Já que o algoritmo expande a árvore por exatamente um vértice em cada iteração, o total é n-1.
        
        A árvore gerada é o conjunto de arestas usadas para as expansões de árvore
        
        É necessário dar a todo vértice fora da árvore info sobre a aresta mais curta conectando a vértice a uma vértice de árvore.
        
        Conseguimos isso anexando duas labels ao vértice:
        
        O nome da vértice de árvore mais próxima
        
        O peso da aresta correspondente.
        
        Vértices não adjecentes às vértices de árvore são dadas o símbolo de infinito, tendo distância "Infinita" das vértices de árvore.
        
        Eficiência
        
        Se um grafo é representado pela sua matriz de peso e a priority queue é uma unordered array, o tempo de duração vai ser Θ(|V|^2)
        
        Também podemos implementar a priority queue como uma min-heap.
        
        Se um grafo é representado por sua lista de adjecência e a priority queue é uma min-heap, o tempo de duração é O(|E| log |V)
      - Algoritmo de Kruskal
        
        Outro algoritmo guloso
        
        Olha uma árvore de extensão mínima de um grafo conectado e com peso G = (V, E) como um subgrafo acíclico com |V| - 1 arestas para quais a soma dos pesos de arestas é o menor possível.
        
        O algoritmo constrói a árvore de extensão mínima como uma sequência expansiva de subgrafos que são sempre acíclicas, mas não necessariamente conectadas nos estágios intermediários do algoritmo.
        
        O algoritmo começa dando sort nas arestas do grafo em ordem não decrescente de peso. Então, começando com um subgrafo vazio, ele escaneia essa sorted list, adicionando a próxima aresta na lista ao atual subgrafo, se tal inclusão não cria um ciclo e simplesmente pulando a aresta se não for o caso.
        
        Tentando ambos esse e Prim podem fazer pensar que Kruskal é mais simples, mas isso é errado.
        
        Eficiência quando o sistema de sorting é eficiente: O(|E| log |E|)
        
        Disjoint Subsets
        
        A maioria de suas implementações usam um elemento de cada disjoint subset em uma coleção como sua representativa
        
        Quick-Find
        
        Usa uma array indexada pelos elementos de sua set S; os valores da array indicam os representativos da subset contendo todos esses elementos. Cada subset é uma linked list cujo header contém os pointers aos primeiros e últimos elementos da lista além do número de elementos na lista.
        
        Quick-Union
        
        Representa cada subset por uma árvore raizada. Os nodes da árvore contém os elementos do subset (um por node), com o elemento da raiz considerada a sua representativa.
        
        Union-Find