ALGORITMO DE PRIM

ALGORITMO DE PRIM

1. COM N PONTOS, IREMOS CONECTÁ-LOS DA MANEIRA MAIS BARATA POSSÍVEL PARA QUE HAJA UM CHAMINHO ENTRE CADA PAR DE ARESTAS

2. PROBLEMA DA ÁRVORE GERADORA MÍNIMA

   • É UM SUBGRAFO ACÍCLICO QUE CONTÉM TODOS OS VÉRTICES DOS GRAFOS
   • CASO HAJA PESOS NAS ARESTAS, UMA ÁRVORE GERADORA MÍNIMA É A EXTENSÃO DA ÁRVORE DE MENOR PESO
     • O PESO DE UMA ÁRVORE É DEFINIDO COMO A SOMA DOS PESOS EM TODAS AS ARESTAS
   • PROBLEMA É ENCONTRAR UMA DESSA PARA CERTO GRAFO CONECTADO PONDERADO

3. SE FOSSE POR BUSCA EXAUSTVA HAVERIAM 2 PROBLEMAS

   • O NUMERO DE ÁRVORES GERADOS CRESCERIA DE FORMA EXPONENCIAL(PELO MENOS PARA GRAFOS DENSOS)
   • GERAR NOVAS ÁRVORES NÃO É FÁCIL

4. CONSTRÓI UMA AVGERMIN POR MEIO DE SEQUÊNCIAS DE SUBÁRVORES DE EXPANSÃO

   • A INICIAL CONSISTE EM UM ÚNICO VERTICE SELECIONADO DO CONJUNTO V DOS VÉRTICES DO GRAFO
   • A CADA ITERAÇÃO EXPANDE A ÁRVORE ATUAL DE MANEIRA GULOSA, ANEXANDO A ELA O VÉRTICE MAIS PRÓXIMO QUE NÃO ESTÁ NA ÁRVORE
   • A ÁRVORE GERADA É OBTIDA COMO CONJUNTO DE ARESTAS QUE NÃO ESTÃO NA ÁRVORE

5. FORNECE INFORMAÇÕES DOS VÉRTICES QUE NÃO ESTÃO NA ÁRVORE: SOBRE A ARESTA MAIS CURTA PARA CONECTAR UM AO OUTRO

   • A FRANJA CONTÉM OS VERTICES QUE NÃO PERTECEM A ÁRVORE MAS SÃO ADJACENTES A PELO MENOS UM VÉRTICE QUE PERTENCE A ELA