Blog de Helton Duarte

Olá pessoal!

Hoje teremos a última parte da aula de grafos (foi dividida em 3), sendo também nossa aula final antes da 2ª fase da OBI. Contudo, o curso Programando Melhor não irá terminar, ele continuará presente no blog, com a apresentação futura de tópicos sobre Programação Dinâmica e alguns assuntos interessantes, conforme eu for descobrindo, ok? Além disso, o blog voltará a ter posts sobre assuntos variados, envolvendo a área de TI em geral, não sendo focado apenas para a parte de Programação (contudo a maioria ainda será de programação, por ser minha “especialidade”).

Aula 8 – Grafos III

Conteúdo: Apresentação de mais alguns conceitos da teoria dos grafos, assim como algoritmos para resolução da Árvore Geradora Mínima e do menor caminho em um grafo valorado.

Teoria dos grafos é o estudo das propriedades das estruturas feitas com grafos. Com ela (a teoria) é possível ter uma linguagem comum ao tratar desse assunto, sendo a chave para resolver muitos problemas o fato de identificar esses conceitos fundamentais e implementar algoritmos clássicos para resolvê-los.

Propriedades dos graus

A propriedade mais simples de um vértice é seu grau, ou seja, a quantidade de arestas que incidem sobre ele. Existem diversas propriedades importantes do grau de um vértice, como a soma de todos os graus ser igual ao dobro do número de arestas, pelo fato desta contribuir para o grau de vértices adjacentes. Uma consequência disso é que qualquer grafo possui um número par de vértices com grau ímpar.

Árvores são grafos indiretos que não contém ciclos. Os graus dos vértices são importantes para a análise de árvores. A folha de uma árvore é um vértice com grau 1. Cada grupo de n vértices, contém n-1 arestas, portanto uma árvore possui no mínimo duas folhas. Ao retirar uma folha diminui-se a árvore, sem disconectá-la.

Uma árvore geradora de um grafo G = (V, E) é um subconjunto de arestas E’ contido em E, tal que E’ é uma árvore com os vértices V. Esse tipo de árvore existe para qualquer grafo conexo (com todos os vértices ligados entre si por algum caminho) e é visto pela relação estabelecida no vetor parent[ ], em buscas em largura e profundidade.

Árvore Geradora Mínima

Utilizada em grafos valorados, a árvore geradora mínima consiste em buscar a árvore geradora que possui a menor soma dos valores de suas arestas. São a resposta ao tratarmos de problemas sempre que precisarmos ligar um conjunto de pontos pela menor quantidade de canos, fios, etc.

Há dois algoritmos principais para tratar de árvores geradoras mínimas, o de Kruskal e o de Prim, contudo irei abordar aqui apenas o segundo, por ser mais simples e nos dar uma ótima base para enterder o menor caminho de Dijkstra, a seguir.

Primeiramente, generalizaresmos a estrutura de grafos implantada nas aulas anteriores, para utilizarmos grafos valorados.

typedef struct {

int v;            /* vértice adjacente */

int valor;    /* valor da aresta */

} aresta;

typedef struct {

edge edges[MAXV+1][MAXGRAU];    /* informação de adjacência */

int grau[MAXV+1];                                    /* grau de cada vértice */

int nvertices;                                                /* número de vértices no grafo */

int narestas;                                                  /* número de arestas no grafo */

} grafo;

OBS: lembrando também de ajeitar a inicialização e as buscas apropriadamente, o que não é trabalho complicado.

O algoritmo de Prim começa de um vértice inicial e a cada iteração é adicionado um novo vértice na árvore geradora, ligando sempre o menor valor de um vértice dentro da árvore para um vértice fora. A implementação abaixo mantém todas as arestas dos vértices já inclusos na árvore para vértices não-inclusos, sendo o menor incluído na próxima iteração.

prim (grafo *g, int start)
{
int i;      /* contador */
bool intree[MAXV];           /* esse vértice está na árvore? */
int distance[MAXV];          /* distância do vértice ao start */
int v;                       /* vértice atual para ser processado */
int w;                       /* candidato para próximo vértice */
int weight;                  /* valor da aresta */
int dist;                    /* menor distância atual */

for (i=1; i<g->nvertices; i++)
{
intree[i] = FALSE;
distance[i] = MAXINT;
parent[i] = -1;
}

distance[start] = 0;
v = start;

while (intree[v] == FALSE) {
intree[v] = TRUE;

for (i=0; i<g->nvertices; i++)
{
w = g->edges[v][i].v;
weight = g->edges[v][i].weight;

if ((distance[w] > weight) && (intree[w] == FALSE))
{
distance[w] = weight;
parent[w] = v;
}
}

v = 1;
dist = MAXINT;

for (i=2; i<=g->nvertices; i++)
{
if ((intree[i] == FALSE) && (dist > distance[i]))
{
dist = distance[i];
v = i;
}
}
}
}

Algumas alterações nesse método podem (e normalmente devem) ser feitas, de acordo com a necessidade do problema, como imprimir cada aresta, à medida que são encontradas ou armazenar o valor da soma de todas as arestas da árvore, para retornar no final. Ou seja, foi dado o queijo e a faca para vocês, resta saberem cortá-lo. Algumas variações são, por exemplo, a árvore geradora máxima (sendo preciso apenas deixar os valores das arestas negativos), árvore com menor produto possível das arestas (substituindo o valor da aresta pelo seu logaritmo).

Menor caminho

O problema de encontrar o menor caminho em grafos não-valorados, já foi discutido na aula anterior, sendo apenas necessário o uso de uma busca em largura, no entanto hoje iremos mostrar um algoritmo básico (e eficiente) para tratar desses “novos tipos de grafos”:  Dijkstra.

Floyd-Warshall é outra opção, mas já fora tratado no aula de Revisão para a primeira fase da OBI, nesse blog, com a aplicação no problema Batuíra, da seção pratique do site da Olimpíada Brasileira de Informática e, portanto, não será mais abordado (deem uma olhada no post de Revisão para entender o código).

O algoritmo de Dijkstra é um método para encontrar o menor caminho entre dois vértices de um grafo valorado. Dado um vértice particular s, ele encontrará o menor caminho de s para qualquer outro vértice do grafo, incluindo o seu destino t.

A idéia é praticamente igual a de Prim, na árvore geradora mínima. A diferença entre eles é como comparar se o próximo vértice é o desejável. No menor caminho nós buscamos o vértice em que a distância até o atual MAIS o seu valor será menor do que o comparado, ou seja:

if (distance[w] > (distance[v]+weight)) {

distance[w] = distance[v] + weight;

parent[w] = v;

}

Ao contrário do algoritmo de Prim, Dijkstra não pode trabalhar com valores negativos, porém esse problema é insignificante, já que não há aplicação prática para tais valores. Não se esqueça de exercitar:

• Freckles – Nível 2
• The Necklace – Nível 3
• Fire Station – Nível 2
• Railroads – Nível 3
• War – Nível 3
• Tourist Guide – Nível 3
• The Grand Dinner – Nível 4
• The Problem With the Problem Setter – Nível 3

PS: Todo o conteúdo desse post e de todo o curso “Programando melhor” é baseado no livro Programming Challenges, de autoria de Miguel Revilla e Steve Skiena e foi permitido o “resumo” e tradução do mesmo pelos próprios autores para a criação desse curso. Além disso os exercícios estão todos disponibilizados no site UVa Online Judge.

Com isso, terminamos nossas dicas antes da 2ª fase da OBI, o que posso fazer agora é desejá-los boa prova e que Deus vos abençoe. Atentem principalmente para os assuntos dos posts recomendados a seguir:

Posts interessantes:

• Programando melhor: Revisão
• Programando melhor: Aula 5 – Backtracking
• Programando melhor: Aula 6 – Grafos I
• Programando melhor: Aula 7 – Grafos II

Vamos lá, estamos na reta FINAL! Comentem e tirem suas dúvidas!

Helton de Melo Duarte

“Os preceitos do SENHOR são retos e alegram o coração; o mandamento do SENHOR é puro e alumia os olhos.” Salmos 19.8

This entry was posted on segunda-feira, maio 4th, 2009 at 16:59 and is filed under Programando Melhor. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.