Algoritmo de Prim

Prévia do material em texto

Algoritmo de Prim
Na ciência da computação o algoritmo de Prim é um algoritmo guloso empregado para encontrar uma árvore geradora mínima (MST), 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 (O algoritmo foi publicado por Prim em 1961 e por Dijkstra pouco depois.).
Outros algoritmos conhecidos para encontrar árvores geradoras mínimas são os algoritmo de Kruskal e o de Boruvka. No entanto estes algoritmos podem ser empregados em grafos desconexos, enquanto o algoritmo de Prim precisa de um grafo conexo.
Algoritmo
Para descrever a aplicação do algoritmo de Prim a um grafo conexo G com custos nas arestas, convém recorrer ao conceito de franja.  A  franja de uma subárvore T de G é o conjunto de todas as arestas de G que têm uma ponta em T e outra ponta fora.   A franja de T nada mais é que o leque do conjunto de vértices de T. 
Cada iteração do algoritmo de Prim começa com uma subárvore T.  No início da primeira iteração, T consiste em um único vértice.  O processo iterativo consiste no seguinte: 
enquanto  a franja de T não é vazia  faça 
seja e uma aresta da franja que tem custo mínimo 
acrescente  e  a  T 
devolva  T 
Como se vê, o algoritmo de Prim tem caráter guloso: em cada iteração, abocanha a aresta que parece mais promissora localmente sem se preocupar com o efeito global dessa escolha.
Grafo Usado: Vamos aplicar o algoritmo de Prim nesse grafo, ele é conexo e valorado.
Passo 1: Iniciaremos a partir do Vértice “0”.
Vértices selecionados: “0”.
Franja: “2, 3”.
Possíveis caminhos: “0-2, 0-3”.
Menor custo: “0-2”
Passo 2:
Vértices selecionados: “0, 2”.
Franja: “1, 3, 4”.
Possíveis caminhos: “0-3, 2-1, 2-3, 2-4”.
Menor custo: “2-4”
Passo 3:
Vértices selecionados: “0, 2, 4”.
Franja: “1, 3, 5, 6”.
Possíveis caminhos: “0-3, 2-1, 2-3, 4-1, 4-3, 4-5, 4-6”.
Menor custo: “4-3”
Passo final:
Implementação com Matriz
Biblioteca
As funções “DIGRAPHinsertA e GRAPHinsertE”, agora recebem um 4º parâmetro que se refere ao valor do caminho (custo).
#include "stdio.h"
#include "stdlib.h"
#define Vertex int
#define Edge Arc
#define EDGE ARC
#define graph digraph
#define Graph Digraph
#define GRAPHinit DIGRAPHinit
#define GRAPHshow DIGRAPHshow
#define maxV 100
typedef struct digraph *Digraph; // Objeto do tipo Digraph contém o endereço de um digraph
typedef struct { // Arco
 Vertex v; // Vértice inicial v
 Vertex w; // Vértice final w
 } Arc;
struct digraph { // Digrafo
 int V; // Número de vértices
 int A; // Número de arestas
 int **adj; // Ponteiro para a matriz de adjacência (são ou não vizinhos)
 };
Arc ARC (Vertex v, Vertex w); // Recebe dois vértices e devolve um arco, com ponto inicial v e final w;
int **MATRIXint (int r, int c, int val); // Aloca uma matriz com linhas r - 1 e colunas c - 1, recebendo um valor val;
Digraph DIGRAPHinit (int v); // Devolve o endereço de um novo digrafo. Inicialização;
void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w, int valor); // Insere arco v-w no digrafo G. Se v == w ou o digrafo já tem arco v-w, não faz nada;
void DIGRAPHshow (Digraph G); // Para cada vértice v de G, imprime em uma linha, os vértices adjacentes a v;
void GRAPHinsertE (Graph G, Vertex v, Vertex w, int valor); // Insere uma aresta v-w no grafo G;
Arc ARC (Vertex v, Vertex w) {
 Arc e;
 e.v = v;
 e.w = w;
 return e;
}
int **MATRIXint (int r, int c, int val) {
 Vertex i, j;
 int **m = malloc(r * sizeof(int *));
 for (i = 0; i < r; i++)
 m[i] = malloc(c * sizeof(int));
 for (i = 0; i < r; i++) {
 for (j = 0; j < c; j++)
 m[i][j] = val;
 }
 return m;
}
Digraph DIGRAPHinit (int v) {
 Digraph G = malloc(sizeof *G);
 G -> V = v;
 G -> A = 0;
 G -> adj = MATRIXint(v, v, 0);
 return G;
}
void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w, int valor) {
 if (v != w && G -> adj[v][w] == 0) {
 G -> adj[v][w] = valor;
 G -> A++;
 }
}
void DIGRAPHshow (Digraph G) {
 Vertex v, w;
 for (v = 0; v < G -> V; v++) {
 printf("%2d: ", v);
 for (w = 0; w < G -> V; w++) {
 if (G -> adj[v][w] != 0)
 printf("%2d ", w);
 }
 printf("\n");
 }
}
void GRAPHinsertE (Graph G, Vertex v, Vertex w, int valor) {
 DIGRAPHinsertA(G, v, w, valor);
 DIGRAPHinsertA(G, w, v, valor);
}
A função Prim
void prim(Graph G, Vertex V) {
 int selecionados[G->V], franja[G->V];
 int i, j, menor_custo = 98;
 Arc arco;
 Graph MST;
 //inicializa os vetores
 MST = DIGRAPHinit(G->V);
 for (i = 0; i < G->V; i++) {
 selecionados[i] = 0;
 franja[i] = 0;
 }
 selecionados[V] = 1;
 while (menor_custo != 99) { // Quando o menor custo for o custo máximo, significará que não tem franja.
 //zera franja
 for (i = 0; i < G->V; i++)
 franja[i] = 0;
 //define franja
 for (i = 0; i < G->V; i++)
 if (selecionados[i] == 1)
 for (j = 0; j < G->V; j++)
 if (G->adj[i][j] != 0 && selecionados[j] == 0)
 franja[j] = 1;
//Escolhe menor custo
 menor_custo = 99; //Inicializa o menor custo com o custo maximo
 for (i = 0; i < G->V; i++)
 if (selecionados[i] == 1)
 for (j = 0; j < G->V; j++)
 if (i != j && franja[j] == 1 && G->adj[i][j] != 0)
 if (G->adj[i][j] < menor_custo && G->adj[i][j] != 0) {
 menor_custo = G->adj[i][j];
 arco.v = i;
 arco.w = j;
 }
 GRAPHinsertE(MST, arco.v, arco.w, 1);
 selecionados[arco.w] = 1;
 selecionados[arco.v] = 1;
 }
 printf("\n\nArvore MST: \n");
 DIGRAPHshow(MST);
}
Implementação com Listas de adjacência
Biblioteca
As funções “DIGRAPHinsertA, GRAPHinsertE e link NEW”, agora recebem um parâmetro adicional que se refere ao valor do caminho (custo). A “struct node” recebe uma nova variável chamada “valor”, que receberá o valor(custo) do arco.
#include "stdio.h"
#include "stdlib.h"
#define Vertex int
#define graph digraph
#define Graph Digraph
#define GRAPHinit DIGRAPHinit
#define GRAPHshow DIGRAPHshow
typedef struct digraph *Digraph; // Objeto do tipo Digraph contém endereço de um digraph
typedef struct node *link; // link é um ponteiro para um node
struct digraph { // Estrutura Digraph
 int V; // Número de vértices
 int A; // Número de arcos
 link *adj; // Ponteiro para um vetor de listas de adjacência
 };
/* A lista de adjacência de um vértice v é composta por nós do tipo node
 Um link é um ponteiro para um node
 Cada nó da lista contém um vizinho w de v e o endereço do nó seguinte da lista */
struct node {
 Vertex w;
 int valor;
 link next;
 };
link NEW (Vertex w, link next, int valor); // Devolve um novo nó x, com x.w = w e x.next = next;
Digraph DIGRAPHinit (int V); // Devolve um novo digrafo com vértices de 0 a V - 1;
void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w, int valor); // Insere um arco v-w, caso v==w ou o arco já exista, não faz nada;
void DIGRAPHshow (Digraph G); // Para cada vértice v de G, imprime em uma linha, os vérticesadjacentes a v;
void GRAPHinsertE (Graph G, Vertex v, Vertex w, int valor); // Insere uma aresta v-w no grafo G;
link NEW (Vertex w, link next, int valor) {
 link x = malloc(sizeof *x);
 x -> w = w;
 x -> valor = valor;
 x -> next = next;
 return x;
}
Digraph DIGRAPHinit (int V) {
 Vertex v;
 Digraph G = malloc(sizeof *G);
 G -> V = V;
 G -> A = 0;
 G -> adj = malloc(V * sizeof(link));
 for (v = 0; v < V; v++)
 G -> adj[v] = NULL;
 return G;
}
void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w, int valor) {
 link p;
 if (v == w)
 return;
 for (p = G -> adj[v]; p != NULL; p = p -> next)
 if (p -> w == w)
 return;
 G -> adj[v] = NEW(w, G -> adj[v], valor);
 G -> A++;
}
void DIGRAPHshow (Digraph G) {
 Vertex v;
 link p;
 for (v = 0; v < G -> V; v++) {
 printf("%2d: ", v);
 for (p = G -> adj[v]; p != NULL; p = p -> next) {
 printf("%2d[%2d] ", p -> w, p->valor);
 }
 printf("\n");
 }
}
void GRAPHinsertE (Graph G, Vertex v, Vertex w, int valor) {
 DIGRAPHinsertA(G, v, w, valor);
 DIGRAPHinsertA(G, w, v, valor);
}
A função Prim
void prim_listas(Graph G, Vertex V) {
 int w, v, valor, i_s, i_f, nodup, menor_custo;
 link p;
 Vertex i, j;
 Vertex selecionados[G->V], franja[G->V], franja_valor[G->V];
 Graph MST;
 //inicializa os vetores
 MST = DIGRAPHinit(G->V);
 for (i = 0; i < G->V; i++) {
 selecionados[i] = 0;
 franja[i] = 0;
 }
 selecionados[V] = 1;
 //loop principal
 while (menor_custo != 99) {// Quando o menor custo for o custo máximo, significará que não tem franja.
 //zera a franja
 for (i = 0; i < G->V; i++)
 franja[i] = 0;
 //define a franja
 for (i = 0, j = 0; i < G->V; i++)
 if (selecionados[i] != 0)
 for (p = G->adj[i]; p != NULL; p = p->next)
 if (p != NULL && selecionados[p->w] == 0){
 //Para não duplicar valores na franja
 nodup = 1;
 for (i_f = 0; franja[i_f] != 0; i_f++)
 if (franja[i_f] == p->w)
 nodup = 0;
 if (nodup == 1) {
 franja[j] = p->w;
 j++;
 }
 }
 //Escolhe menor custo
 menor_custo = 99; //Inicializa o menor custo com o custo maximo
 for (i = 0, j = 0; i < G->V; i++)
 if (selecionados[i] != 0)
 for (p = G->adj[i]; p != NULL; p = p->next)
 if (p != NULL && p->valor < menor_custo ) {
 //evita escolher um uma aresta contendo 2 selecionados
 nodup = 1;
 for (i_s = 0; i_s < G->V; i_s++)
 if (selecionados[i_s] == 1 && i_s == p->w)
 nodup = 0;
 if (nodup == 1) {
 menor_custo = p->valor;
 v = i;
 w = p->w;
 valor = p-> valor;
 }
 }
 GRAPHinsertE(MST, v, w, valor);
 selecionados[w] = 1;
 selecionados[v] = 1;
 }
 printf("\n\nArvore MST: \n");
 DIGRAPHshow(MST);
}
Fontes:
www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/prim.html
http://pt.wikipedia.org/wiki/Algoritmo_de_Prim