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 Clay Prim em 1957 e redescoberto por Edsger Dijkstra em 1959.
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
Um algoritmo genérico para o algoritmo de Prim é dado da seguinte forma:
Escolha um vértice S para iniciar o subgrafo
enquanto houver vértices que não estão no subgrafo
selecione uma aresta segura
insira a aresta segura e seu vértice no subgrafo
Pseudocódigo
prim(G) # G é grafo
# Escolhe qualquer vértice do grafo como vértice inicial/de partida
s ← seleciona-um-elemento(vertices(G))
para todo v ∈ vertices(G)
π[v] ← nulo
Q ← {(0, s)}
S ← ø
enquanto Q ≠ ø
v ← extrair-mín(Q)
S ← S ∪ {v}
para cada u adjacente a v
se u ∉ S e pesoDaAresta(π[u]→u) > pesoDaAresta(v→u)
Q ← Q \ {(pesoDaAresta(π[u]→u), u)}
Q ← Q ∪ {(pesoDaAresta(v→u), u)}
Q <- Q u {pesoDaArest(v->)%2, Q++}
π[u] ← v
print(Pronto)
retorna {(π[v], v) | v ∈ vertices(G) e π[v] ≠ nulo}
π[v] indica o predecessor de v. Após o término do algoritmo, para cada v pertencente aos vértices de G, π[v]→v representa uma aresta selecionada para a árvore geradora mínima se π[v] ≠ nulo. O algoritmo retorna o conjunto dessas arestas, formado pelos pares (π[v], v).
Q é um conjunto de pares (peso, vértice). O método extrair-mín(Q) deve extrair o menor elemento de Q; um par (a,b) é menor que um par (c,d) se a < c ou se a = c e b < d.
S é um conjunto que armazena os vértices cujas adjacências já foram analisadas.
Complexidade
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
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é então 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.
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.
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ções
Implementação em C
intprimMST(LAdj*g,intp[],intw[]){inti,imin,v,r=0,cor[g->nvert];Nodo*aux;intfsize=0,fringe[g->nvert];// ORLA (stack de vértices)// Inicializações...for(i=0;i<g->nvert;i++){p[i]=-1;cor[i]=BLACK;}cor[0]=GREY;w[0]=0;fringe[fsize++]=0;//f = addV(f, 0, 0);//ciclo principal...while(fsize>1){// Retirar melhor elemento da orla ("f = nextF(f, &v);"):// (1) encontrar mínimoimin=0;for(i=1;i<fsize;i++)if(w[fringe[imin]]<w[fringe[i]])imin=i;// (2) remover elementov=fringe[imin];fringe[imin]=fringe[++fsize];// FIM DE "retirar"cor[v]=BLACK;r+=w[v];for(aux=g->adj[v];aux;aux=aux->prox)switch(cor[aux->dest]){caseWHITE:cor[aux->dest]=GREY;fringe[fsize++]=aux->dest;//f = addV(f, aux->dest, aux->peso);w[aux->dest]=aux->peso;p[aux->dest]=v;break;caseGREY:if(aux->peso>w[aux->dest]){//f = updateV(f, aux->dest, aux->peso);p[aux->dest]=aux->peso;w[aux->dest]=v;}default:break;}}returnr;}
Implementação em Python
A implementação a seguir usa uma lista de adjacência para representar o grafo. A complexidade de tempo é . Uma função adicional, primDesconexo, resolve o problema para grafos desconexos, sem alterar a complexidade de tempo do algoritmo.
# Implementacao do algoritmo de Prim O(E log V) em Python# Note que a unica funcao que representa a implementacao do algoritmo eh a funcao prim(graph,Vi=0,edge=[],vis=[])# A funcao add_edge eh apenas auxiliar, e a funcao primDesconexo(graph) eh um adicional, e nao costuma sequer ser# implementada para o algoritmo de Prim (pois no caso de um grafo ser desconexo, Kruskal eh a solucao ideal).fromheapqimportheappop,heappushMAXV=1000# numero de vertices no grafograph=[[]forxinxrange(MAXV)]defadd_edge(v,u,w):graph[v].append((u,w))graph[u].append((v,w))# considera que o grafo eh nao direcionado# Se o grafo for totalmente conectado, Vi pode receber qualquer vertice sem diferenca no peso total da arvore gerada# Se o grafo for desconexo, apenas a parte conectada a Vi tera sua arvore geradora minima calculada# O retorno eh uma lista de tuplas edge[v]=(w,u), que representa, para cada v, a aresta u->v com peso w, usada para# conectar a sub-arvore de v a sub-arvore de u na arvore geradora minimadefprim(graph,Vi=0,edge=[],vis=[]):# edge[v] = (pesoDaAresta(u->v), u)# Se edge[] ou vis[] nao tiverem sido gerados ainda, geramos. Geralmente esta condicao nao existe, e ambas as listas# sao geradas dentro do proprio prim; porem, para manter o primDesconexo em O(V + E log V), permitimos que sejam# passadas pelos parametros da funcao.ifedge==[]:edge=[(-1,-1)]*len(graph)ifvis==[]:vis=[False]*len(graph)edge[Vi]=(0,-1)heap=[(0,Vi)]whileTrue:v=-1whilelen(heap)>0and(v<0orvis[v]):v=heappop(heap)[1]ifv<0oredge[v][0]<0:breakvis[v]=Truefor(u,w)ingraph[v]:ifedge[u][0]<0oredge[u][0]>w:edge[u]=(w,v)heappush(heap,(edge[u][0],u))returnedge# Se o grafo for desconexo, pode-se usar:defprimDesconexo(graph):edge=[(-1,-1)]*len(graph)vis=[False]*len(graph)foriinxrange(len(graph)):ifedge[i][0]==-1:prim(graph,i,edge,vis)returnedge
Implementação em PHP
$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 custoechoutf8_decode("Grafo:<br>");for($i=1;$i<=count($origem);$i++){echoutf8_decode("$origem[$i]$destino[$i]$custo[$i]<br>");}// ------ Passo inicial// Seta os valores de Tfor($i=1;$i<=6;$i++){if($i==1){$t[$i]=$i;}else{$t[$i]="nulo";}}// Seta os valores de Vfor($i=1;$i<=6;$i++){if($i==1){$v[$i]="nulo";}else{$v[$i]=$i;}}echoutf8_decode("Início");echoutf8_decode("<br> T: ");print_r($t);echoutf8_decode("<br> V: ");print_r($v);echoutf8_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;echoutf8_decode("<br> Aresta ($origem[$aux],$destino[$aux]) escolhida de custo $custo[$aux]");}else{$minimo=$minimo2;$aux=$aux2;echoutf8_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";}echoutf8_decode("<br> ".$x."° iteração");echoutf8_decode("<br> T: ");print_r($t);echoutf8_decode("<br> V: ");print_r($v);}
Referências
Bibliografia
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. ISBN0-262-03293-7A referência emprega parâmetros obsoletos |coautor= (ajuda)
