Top Qs
Linha do tempo
Chat
Contexto
Algoritmo de Prim
Da Wikipédia, a enciclopédia livre
Remove ads
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.
Outros algoritmos conhecidos para encontrar árvores geradoras mínimas são o algoritmo de Kruskal e algoritmo de Boruvka, sendo que este último pode ser empregado em grafos desconexos, enquanto o algoritmo de Prim e o Algoritmo de Kruskal precisam de um grafo conexo.
Remove ads
Descrição
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
- enquanto houver vértices que não estão no subgrafo
Remove ads
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.
Remove ads
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
Resumir
Perspectiva
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.
Remove ads
Implementações
Implementação em C
int primMST(LAdj *g, int p[], int w[]) {
int i, imin, v, r=0, cor[g->nvert];
Nodo *aux;
int fsize=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ínimo
imin = 0;
for (i=1; i<fsize; i++)
if (w[fringe[imin]] < w[fringe[i]]) imin = i;
// (2) remover elemento
v = 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])
{
case WHITE:
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;
case GREY:
if (aux->peso > w[aux->dest]) {
//f = updateV(f, aux->dest, aux->peso);
p[aux->dest] = aux->peso;
w[aux->dest] = v;
}
default:
break;
}
}
return r;
}
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).
from heapq import heappop, heappush
MAXV = 1000 # numero de vertices no grafo
graph = [[] for x in xrange(MAXV)]
def add_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 minima
def prim(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.
if edge == []:
edge = [(-1,-1)] * len(graph)
if vis == []:
vis = [False] * len(graph)
edge[Vi] = (0,-1)
heap = [(0,Vi)]
while True:
v = -1
while len(heap) > 0 and (v < 0 or vis[v]):
v = heappop(heap)[1]
if v < 0 or edge[v][0] < 0:
break
vis[v] = True
for (u, w) in graph[v]:
if edge[u][0] < 0 or edge[u][0] > w:
edge[u] = (w, v)
heappush(heap, (edge[u][0],u))
return edge
# Se o grafo for desconexo, pode-se usar:
def primDesconexo(graph):
edge = [(-1,-1)] * len(graph)
vis = [False] * len(graph)
for i in xrange(len(graph)):
if edge[i][0] == -1:
prim(graph, i, edge, vis)
return edge
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 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);
}
Remove ads
Referências
Bibliografia
Ligações externas
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads