Usuário:Aexpedito/Prim

Origem: Wikipédia, a enciclopédia livre.

Na ciência da computação o algoritmo de Prim é um algoritmo guloso (greedy algorithm) empregado para encontrar uma árvore geradora mínima (minimal spanning tree) num grafo conectado, valorado e não direcionado. Isso significa que o algoritmo encontra um subgrafo do grafo original no qual a soma total das arestas é minimizada e todos os vértices estão interligados. O algoritmo foi desenvolvido em 1930 pelo matemático Vojtěch Jarník e depois pelo cientista da computação Robert C. Prim em 1957 e redescoberto por Edsger Dijkstra em 1959.

Outros algoritmos conhecidos para encontrar árvores geradoras mínimas são o algoritmo de Kruskal e algoritmo de Boruvka. No entanto estes algoritmos podem ser empregados em grafos desconexos, enquanto o algoritmo de Prim precisa de um grafo conexo.

Descrição[editar | editar código-fonte]

Figura 1: passo a passo da execução do algoritmo de Prim iniciado pelo vértice 0

O algoritmo de Prim encontra uma árvore geradora mínima para um grafo desde que ele seja valorado e não direcionado. Por exemplo, se na figura 1 os vértices deste grafo representassem cidades e as arestas fossem estradas de terra que interligassem estas cidades, como poderíamos determinar quais estradas asfaltar gastando a menor quantidade de asfalto possível para interligar todas as cidades. O algoritmo de Prim neste caso fornecerá uma resposta ótima para este problema que não necessariamente é única. A etapa f) da figura 1 demonstra como estas cidades devem ser conectadas com as arestas em negrito.

Algoritmo genérico[editar | editar código-fonte]

Um algoritmo genérico para o algoritmo de Prim é dado da seguinte forma:

Escolha um vértice S para iniciar o subgrafo
enquanto há vértices que não estão no subgrafo
selecione uma aresta segura
insira a aresta segura e seu vértice no subgrafo



Complexidade[editar | editar código-fonte]

A complexidade do algoritmo de Prim pode mudar de acordo com a estrutura de dados utilizada para representar o grafo. As implementações mais comuns para um grafo são por listas de adjacência e por matrizes de adjacência e suas respectivas complexidades e no pior caso.

Exemplo de execução[editar | editar código-fonte]

Repare neste exemplo de execução do algoritmo como as arestas são escolhidas para entrar no subgrafo. O conjunto V\U são os vértices que ainda não entraram no subgrafo, o conjunto U são os vértices que já estão no subgrafo, as arestas possíveis é uma lista de arestas que poderiam ser incluidas no subgrafo, pois conectam vértices contidos no subgrafo com os que ainda não estão e as arestas incluídas são aquelas que já estão no subgrafo. Dessa maneira e segundo o algoritmo genérico dado acima, para escolhermos uma aresta segura devemos observar o conjunto de arestas possíveis e selecionar aquelas que não formam ciclos com o subgrafo até entao formado e cujo peso é o mínimo possível naquele momento. Se uma aresta apresentar todos estes quesitos podemos considerá-la uma aresta segura.

Imagem Arestas incluídas
no subgrafo
U Arestas possíveis V \ U Descrição
{} {} {A,B,C,D,E,F,G} Este é o grafo original. Os números próximos das arestas significam o seu peso.
{DA} {D} {D,A} = 5V
{D,B}=9
{D,E}=15
{D,F}=6
{A,B,C,E,F,G} O vértice D foi escolhido como ponto inicial do algoritmo. Vértices A, B, E e F estão conectados com D através de uma única aresta. A é o vértice mais próximo de D e, portanto a aresta AD será escolhida para formar o subgrafo.
{DA, DF} {A,D} {D,B}=9
{D,E}=15
{D,F}=6V
{A,B}=7
{B,C,E,F,G} O próximo vértice escolhido é o mais próximo de D ou A. B está a uma distância 9 de D, E numa distância 15 e F numa distância 6. E A está a uma distância de 7 de B. Logo devemos escolher a aresta DF, pois é o menor peso.
{DA, DF, AB} {A,D,F} {D,B}=9
{D,E}=15
{A,B}=7V
{F,E}=8
{F,G}=11
{B,C,E,G} Agora devemos escolher o vértice mais próximo dos vértices A, D ou F. A aresta em questão é a aresta AB.
{DA, DF, AB, BE} {A,B,D,F} {B,C}= 8
{B,E}=7V
{D,B}=9ciclo
{D,E}=15
{F,E}=8
{F,G}=11
{C,E,G} Agora podemos escolher entre os vértices C, E, e G. C está a uma distância de 8 de B, E está a uma distância 7 de B e G está a 11 de F. E é o mais próximo do subgrafo e, portanto escolhemos a aresta BE.
{DA, DF, AB, BE, EC} {A,B,D,E,F} {B,C}=8
{D,B}=9ciclo
{D,E}=15ciclo
{E,C}=5V
{E,G}=9
{F,E}=8 ciclo
{F,G}=11
{C,G} Restam somente os vértices C e G. C está a uma distância 5 de E e de G a E 9. C é escolhido, então a aresta EC entra no subgrafo construído.
{DA, DF, AB, BE, EC, EG} {A,B,C,D,E,F} {B,C}=8ciclo
{D,B}=9ciclo
{D,E}=15ciclo
{E,G}=9V
{F,E}=8ciclo
{F,G}=11
{G} Agora só resta o vértice G. Ele está a uma distância de 11 de F, e 9 de E. E é o mais próximo, então G entra no subgrafo conectado pela aresta EG.
{DA, DF, AB, BE, EC, EG} {A,B,C,D,E,F,G} {B,C}=8 ciclo
{D,B}=9 ciclo
{D,E}=15 ciclo
{F,E}=8 ciclo
{F,G}=11 ciclo
{} Aqui está o fim do algoritmo e o subgrafo formado pelas arestas em verde representam a árvore geradora mínima. Nesse caso esta árvore apresenta a soma de todas as suas arestas o número 39.

Implementação em PHP[editar | editar código-fonte]

 
 $origem = array( 1 => 1,1,2,2,2,3,4,4,5);
 $destino = array( 1 => 2,3,3,4,5,5,6,5,6);
 $custo = array( 1 => 1,3,1,2,3,2,3,-3,2);
 $nos = 6;
 $narcos = 9;
 
 // Define o infinito como sendo a soma de todos os custos
 $infinito = array_sum($custo);
 
 // Imprimindo origem destino e custo
 echo utf8_decode("Grafo:<br>");
 
 for($i =1 ; $i <= count($origem) ; $i++) {
  echo utf8_decode("$origem[$i] $destino[$i] $custo[$i]<br>");
 }
 
 // ------ Passo inicial
 
 // Seta os valores de T
 for($i =1 ; $i <= 6 ; $i++) { 
   if($i == 1) {
      $t[$i] = $i;
   } else {
      $t[$i] = "nulo";
   }
 }
 
 // Seta os valores de V
 for($i =1 ; $i <= 6 ; $i++) { 
   if($i == 1) {
      $v[$i] = "nulo";
   } else {
      $v[$i] = $i;
   }
 }
 
 echo utf8_decode("Início");
 echo utf8_decode("<br> T: ");
 print_r($t);
 echo utf8_decode("<br> V: ");
 print_r($v);
 echo utf8_decode("<br>");
 
 // ------ Fim do passo inicial
 $total_nos = count($origem);
 for($x =1 ; $x <= ($nos-1) ; $x++) {
        // Verifica origem -> destino
        $minimo1 = $infinito;
        for($i =1 ; $i <= $narcos ; $i++) {
               for($j =1 ; $j <= $nos ; $j++) {
                        if($origem[$i] == $t[$j]) {
                                for($k =1 ; $k <= $nos ; $k++) {
                                        if($destino[$i] == $v[$k]) {
                                                if($custo[$i] < $minimo1) {
                                                      $minimo1 = $custo[$i];
                                                      $aux1 = $i;
                                                }
                                        }
                                }
                        }
               }
        }
 
        // Verifica destino -> origem
        $minimo2 = $infinito;
        for($i =1 ; $i <= $narcos ; $i++) {
                for($j =1 ; $j <= $nos ; $j++) {
                        if($destino[$i] == $t[$j]) {
                                for($k =1 ; $k <= $nos ; $k++) {
                                        if($origem[$i] == $v[$k]) {
                                                if($custo[$i] < $minimo2) {
                                                      $minimo2 = $custo[$i];
                                                      $aux2 = $i;
                                                }
                                        }
                                }
                        }
                }
        }
 
        if($minimo2 < $minimo1) {
              $cont = 1;
              $minimo = $minimo1;
              $aux = $aux1;
              echo utf8_decode("<br> Aresta ($origem[$aux],$destino[$aux]) escolhida de custo $custo[$aux]");
        } else {
              $minimo = $minimo2;
              $aux = $aux2;
              echo utf8_decode("<br> Aresta ($destino[$aux],$origem[$aux]) escolhida de custo $custo[$aux]");
              $cont = 2;
        }
        if($cont == 1) {
              $t[$destino[$aux]] = $destino[$aux];
              $v[$destino[$aux]] = "nulo";
        } else {
              $t[$origem[$aux]] = $origem[$aux];
              $v[$origem[$aux]] = "nulo";		
        }
 
        echo utf8_decode("<br> ".$x."° iteração");
        echo utf8_decode("<br> T: ");
        print_r($t);
        echo utf8_decode("<br> V: ");
        print_r($v);}


Referências

Bibliografia[editar | editar código-fonte]

  • Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2001). «23». Introduction to Algorithms (em inglês) 2 ed. [S.l.]: MIT Press and McGraw-Hill. ISBN 0-262-03293-7 

Ligações Externas[editar | editar código-fonte]

Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.