Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmo de Prim - Coggle Diagram

- - - - O problema da spanning tree mínima é o problema de
        encontrar uma árvore tree mínima para um determinado grafo conectado ponderado.
        
        Se fosse feita a construção de uma spanning tree pelo modo de busca exaustiva iria ter dois problemas
        
        o numero de spanning trees aumentam exponencialmente com o tamanho do grafo
        
        e o processo de gerar não e facil
        
        por isso existe o algoritmo de prim
- - - - ou seja, escolha sempre o vertice de menos custo sem que forme um ciclo
        
        se há 7 vertices, haverá v-1 arestas
        
        sendo o tempo teta(n^2)
        
        mas esse algoritmo pode ser melhorado utilizando heap minima
  - - - o peso minimo de arestas que nao estao na spanning tree é sempre maior que o peso das duas arestas escolhidas
        
        so tera um resultado, ou seja, uma solucao optimal