Usuário:Aexpedito/Prim
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
editarO 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
editarUm 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
- enquanto há vértices que não estão no subgrafo
Complexidade
editarA 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
editarRepare 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.
Implementação em PHP
editar
$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- 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