Blog de Helton Duarte

Olá pessoal,

Hoje iniciaremos um assunto pedido a muito tempo por meus conhecidos: os tão temidos grafos! Contudo, eu já posso adiantar que eles não são complicados como vocês pensam, pelo menos o nível cobrado na OBI. Os conceitos principais podem ser vistos em diversos locais, como nos sites da UFSC e USP, sendo essa uma área muito ampla da computação, recebendo muitas vezes uma disciplina completa nos cursos de Ciência e Engenharia da Computação. Para quem gosta de matemática, há também uma oportunidade de estudá-la, como no curso de iniciação científica da OBMEP.

Aula 6 – Grafos I

Conteúdo: introdução aos conceitos, juntamente com as formas de utilizá-los no campo da computação.

Grafos são um dos temas mais interessantes da ciência da computação – uma representação abstrata que descreve a organização de sistemas de transporte, circuitos elétricos, linhas de telecomunicações, etc. Tantas estruturas diferentes podem ser modeladas utilizando esse conceito, tornando-o uma grande fonte de resolução de problemas. Será vistos hoje apenas o elementar dessa teoria, pela sua vasta abrangência, deixando os algoritmos mais específicos para as próximas aulas.

Tipos de Grafos

Um grafo G = (V, A) é definido por um conjunto de vértices V e um conjunto de arestas A, as quais consistem em pares de vértices contidos em V. Há diversas propriedades fundamentais dos grafos que influenciam na escolha de estruturas de dados  utilizadas para representá-los e os algoritmos para analisá-los. Vamos determinar quais são essas propriedades:

• Indireto vs. Direto - Um grafo G = (V, A) é indireto se a aresta (x, y) pertencer a A e isso implicar que (y, x) também pertence. Se não, é tido como grafo direto. Ex: Ligações por estradas entre cidades são tipicamente indiretas, porque as estradas são de mão-dupla.
• Valorado vs. Não-Valorado - Em grafos valorados, cada aresta (ou vértice) de G é assinalada com um valor numérico, ou peso. Uma aplicação típica são estradas, as quais são valoradas com a distância ou o tempo para percorrê-la. A diferença entre esses tipos é basicamente para encontrar o menor “caminho” entre dois vértices.
• Simples vs. Não-Simples – Certos tipos de arestas complicam a tarefa de trabalhar com grafos. Um laço é uma aresta (x, x) envolvendo somente um vértice. Uma aresta (x, y) é múltipla se ocorre mais de uma vez no mesmo grafo. Um grafo que não possui nenhum desses tipos de aresta é chamado Grafo Simples.

Estrutura de Dados para Grafos

Há muitas formas possíveis de representar um grafo, por isso nos focalizaremos nas mais comuns e úteis. Será assumido o grafo G = (V, A) contendo n vértices e m arestas.

• Matriz de adjacência – Nós podemos representar G usando uma matriz M n x n, onde o elemento M[i,j] é 1 se (i, j) é uma aresta de G e 0 (zero) se não for. Isso permite respostas rápidas para a questão “(i,j) está em G?” e atualizações rápidas para inserir ou deletar arestas. Todavia, esse tipo de representação pode usar espaço excessivo na memória, ao ter muitos vértices e poucas arestas.
• Listas de adjacência – Uma forma mais eficiente de representar é usando listas encadeadas para guardar os adjacentes a cada vértice. Esse tipo requer ponteiros mas não tenha medo se já passou por experiências desagradáveis com eles. Listas de adjacência dificulta para saber se (i, j) está em G, contudo é MUITO mais econômico com memória.
• Listas de Adjacência em Matrizes – Listas de adjacências podem estar embutidas em matrizes, eliminando a necessidade de ponteiros. Nós podemos representar a lista em um vetor (ou na linha de uma matriz) mantendo um contador k de quantos elementos há e colocando-os nos primeiros k elementos do vetor. Agora é possível visitar os elementos do primeiro ao último da mesma forma deuma lista, mas incrementando o índice em um loop ao invés de ponteiros. Esse forma é particularmente importante no caso de grafos estáticos, os quais não mudam após sua construção e será sempre utilizada nos exemplos seguintes.

Nós representamos um grafo usando a seguinte estrutura de dados: para cada grafo nós contabilizamos o número de vétices e os assinalamos de 1 a nvertices. As arestas estão em uma matriz MAXV x MAXGRAU, para cada vértice poder ser adjacente a outros MAXGRAU. Podemos definir MAXGRAU como MAXV, contudo isso seria desperdício em casos de grafos com graus baixos.

#define MAXV 100;              /* máximo número de vértices */

#define MAXGRAU 50;       /* máximo grau de um vértice */

typedef struct {

int arestas [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;

Para demonstrar o uso dessa estrutura de dados, nós mostraremos como ler um grafo, tendo uma linha inicial o número de vértices e arestas no grafo, seguido por uma lista de arestas com um par de vértices por linha.

ler_grafo (grafo *g, bool direto)

{

int i;          /* contador */

int m;       /* número de arestas */

int x, y;   /* vértices em uma aresta (x, y) */

inicializar_grafo (g);

scanf (“%d %d”, &(g->nvertices), &m);

for (i = 1; i <= m; i++) {

scanf (“%d %d”, &x, &y);

inserir_aresta (g, x, y, direto);

}

}

inicializar_grafo (grafo *g)

{

int i;            /* contador */

g->nvertices = 0;

g->narestas = 0;

for (i = 1; i <= MAXV; i++) g->grau[i] = 0;

}

O método principal é o inserir_aresta. O parâmetro Boolean direto é utilizado para identificar quando é preciso inserir duas cópias de cada aresta ou só uma. Preste atenção no uso da recursão para resolver o problema.

inserir_aresta (grafo *g, int x, int y, bool direto)

{

if (g->grau[i] > MAXGRAU)

printf (“Atenção: a inserção (%d, %d) excede o grau máximo\n”, x, y);

g->arestas[x][g->grau[x]] = y;

g->grau[x] ++;

if (direto == FALSE) inserir_aresta(g, y, x, TRUE)

else g->narestas ++;

}

Agora, a tarefa de imprimir o grafo é um trabalho bem simples:

imprimir_grafo (grafo *g)

{

int i, j;                 /* contadores */

for (i = 1; i <= g->nvertices; i++) {

printf (“%d:  “, i);

for (j = 0; j <= g->grau[i]; j++) {

printf (” %d”, g->arestas[i][j]);

}

printf (“\n”);

}

}

Bem pessoal, por hoje é só. Infelizmente, os algoritmos de manipulação mais específica de um grafo ficarão para a próxima aula, ok? E, como foram dados apenas conceitos, excepicionalmente hoje não haverá seção de exercícios. =(

Posts interessantes:

• Programando melhor: Aula 5 – Backtracking
• Programando melhor: Revisão
• Programando melhor: Aula 4 – Ordenação
• Programando melhora: Aula 3 – Strings

O que vocês acharam de grafos? Qualquer dúvida é só Comentar! Para treinar, façam os exercícios da apostila de grafos da iniciação científica da OBMEP, indicada no início, pois são muito bons. Além do mais, qualquer erro, principalmente na parte de código, porque é frequente o WordPress deixar estranho, é só avisar por comentário, ok?

Helton de Melo Duarte

“A minha alma disse ao SENHOR: Tu és o meu SENHOR; não tenho outro além de ti.” Salmos 16.2

This entry was posted on sábado, abril 18th, 2009 at 22:40 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.