Please enable JavaScript.

Coggle requires JavaScript to display documents.

GREEDY TECHNIQUE - Coggle Diagram

- - - - Localmente ótima, deve ser a melhor escolha local entre todas as escolhas viáveis disponíveis naquele passo
        
        Irreversível: uma vez feita não pode ser alterada nos passos subsequentes do algoritmo.
- - - - o peso de uma árvore é a soma dos pesos em todas as suas arestas
        
        o algoritmo de Prim constrói uma árvore geradora mínima por meio de uma sequência de expansão de subárvores.
        
        o algoritmo de Prim sempre gera uma árvore geradora mínima
        
        o tempo de execução do algoritmo de Prim é: O(|E|log|V|)
- - - - o algoritmo começa ordenando as arestas do grafo em ordem não decrescente de seus pesos
        
        em seguida, começando com o subgrafo vazio, ele percorre essa lista ordenada
        
        adicionando a próxima aresta ao grafo atual se essa inclusão não criar um ciclo, e pulando a aresta caso contrário
        
        com um algoritmo de ordenação eficiente, a eficiência temporal do algoritmo de Kruskal será O(|E| log|E|)