Grafos e suas aplicações – parte 2

Leia o artigo anterior

Grafos e suas aplicações

*

No último artigo fiz uma introdução sobre grafos. Hoje vou falar de maneira mais prática sobre o assunto e aplicar em um exemplo prático.

Para se trabalhar com grafos, precisamos analisar a melhor forma de se construir a estrutura de dados para o problema específico. Isso quer dizer que devemos ver quais informações serão necessárias para resolvê-lo.

Armazenar o menor número de informações é importante, já que quando trabalhamos com grafos, na maioria das vezes, trabalhamos com muitos dados. Assim, quanto mais informações se tem na estrutura principal, mais pesada fica a aplicação, já que as operações de ordenação, gets, sets, loops, sobre os dados, comparações etc ficam sobrecarregadas.

Vamos fazer um exemplo prático: uma pessoa possui muitos atributos, como cor dos olhos, do cabelo, altura, peso, idade e muitos outros. Mas se estivermos criando um programa para analisar qual é a maior família existente em determinado bairro ou cidade, nenhum desses dados será útil. Para resolver esse problema, poderíamos ter apenas a informação de quem são os pais de cada pessoa e, com um algoritmo simples da Teoria dos Grafos, podemos resolvê-lo.

Vamos modelar o problema acima como um grafo. Vou escrever o código com C, já que é uma linguagem acadêmica e que é a base de muitas outras linguagens como PHP e Java (não contando a parte de orientação a objetos, que veio da Smalltalk).

Dizer que uma pessoa é filha de outra, no nosso caso, é dizer que um nó é adjacente a outro. Se estamos fazendo um estudo no bairro inteiro, logo a nossa estrutura de dados precisa comportar o número total de pessoas do bairro, que é todo o domínio do problema. A parte abaixo de código ilustra um grafo que comporta 1000 pessoas.

int pessoa[1000][1000];

Sim, uma matriz bidimencional, porque nela iremos colocar as relações entre uma pessoa e outra. Se a cidade tem mil pessoas, cada pessoa pode se relacionar com qualquer outra na cidade, e é na segunda dimensão que guardamos isso.

O segundo passo é: como definir uma relação entre pai e filho? Primeiro, vamos definir como será o valor padrão, ou seja, quando não houver uma relação entre uma pessoa com outra. Para isso vamos usar um número negativo qualquer, por exemplo -1.

Agora podemos popular o grafo da seguinte maneira: cada pessoa do bairro terá um código associado a ela e terá o código dos seus pais também. O código pode ser de 0 a 999, já que temos um vetor numérico simples, se quiséssemos ter um código que aceitasse uma string ou um objeto, teríamos que mudar o vetor para um map, por exemplo. Vamos ao exemplo. Uma pessoa de código 20 tem os pais com código 2 e 3, uma pessoa com código 60 tem os pais 6 e 10 e, por último, uma pessoa com código 40 é filha do 20 e do 30. Para ficar mais fácil, vou escrever com o nome também, nas colunas de pai e mãe vou colocar o nome com o código entre parênteses, assim:

A maior família nesse caso, e a seguinte: 40, 30, 20, 2,3… Ou seja, uma família de cinco pessoas.

A menor família é a única outra: 60, 6, 10… Ou seja, uma família de três pessoas.

Em um caso com apenas três entradas é até possível de se criar um algoritmo de tentativas e erros para achar a maior família, mas imagine uma entrada de 600 casos?

No exemplo da tabela acima poderíamos armazenar o primeiro caso assim:

pessoa[20][2] = 1; /*Fernando tem relação com Joaquim*/<br />pessoa[2][20] = 1; /*Vice-versa*/<br />pessoa[20][3] = 1; /*Fernando tem relação com Maria*/<br />pessoa[3][20] = 1; /*Vice-versa*/

Com essa idéia podemos popular com os outros itens e adicionar mais…

Para resolver o problema basta aplicar o algoritmo de busca em grafos chamado DFS, que navega pelos nós do grafo enquanto tiver novas adjacências não visitadas. A idéia dele é, a partir de um ponto inicial, fazer uma varredura por todos os outros nós adjacentes a ele, marcar esse ponto como visitado para não voltar nele novamente, e refazer os passos do algoritmo, utilizando esse ponto como inicial.

Segue abaixo como seria essa função em C:

void dfs(k)<br />{<br />   int i;<br />   contador++;<br />   if(flag[k]==-1){<br />    flag[k]=1;<br />    for(i=0;i<1000;i++)<br />    {<br />    if(pessoa[k][i]!=-1 && flag[i]==-1)<br />     dfs(i);<br />    }    <br />   }<br />}

Essa função incrementa um contador e utiliza um vetor chamado flag, que deve ser declarado anteriormente. O contador tem que ser zerado e o vetor inicializado com valores padrão de -1. No final, essa função terá incrementado o contador com o número de pessoas máximo encontrado a partir de k. Portanto, essa função deve ser chamada dentro de um loop para cada código de pessoas. Abaixo vou colocar o código inteiro feito em C, vou deixar comentado, para que seja de fácil modificação para qualquer outra linguagem.

/**<br /> * Codigo para artigo no iMasters<br /> * Alantiel Freire Marins<br /> * Entradas usadas no artigo: <br /> * Numero de casos: 3<br /> * Morador 1: 20, pai: 2, mae: 3<br /> * Morador 2: 60, pai: 6, mae: 10<br /> * Morador 3: 40, pai: 20, mae: 30<br /> */<br />#include<stdio.h>  //biblioteca de input/output padrão<br />#include<string.h> //importa biblioteca para que memset possa ser usada<br />int flag[1000],pessoa[1000][1000],contador;<br />void dfs(k)<br />{<br />   int i;<br />   contador++;<br />   if(flag[k]==-1){<br />    flag[k]=1;<br />    for(i=0;i<1000;i++)<br />    {<br />    if(pessoa[k][i]!=-1 && flag[i]==-1)<br />     dfs(i);<br />    }    <br />   }<br />}<br />int main()<br />{<br />   int n,x,y,i,j,maiorFamilia;<br />   printf("Digite o numero de casos: ");<br />   scanf("%d",&n);<br />   memset(flag,-1,sizeof(flag));     //inicializa todos os indices de flag com -1<br />   memset(pessoa,-1,sizeof(pessoa)); //inicializa todos os indices de pessoa com -1<br />   maiorFamilia = -1;<br />   for(i=0;i<n;i++)<br />   {<br />      printf("Digite o codigo o morador %d: ",i+1);      <br />      scanf("%d",&x);<br />      printf("Digite o codigo do pai do morador %d: ",x); <br />      scanf("%d",&y);<br />      pessoa[x][y] = 1;<br />      pessoa[y][x] = 1;<br />      printf("Digite o codigo da mae do morador %d: ",x); <br />      scanf("%d",&y);<br />      pessoa[x][y] = 1;<br />      pessoa[y][x] = 1;<br />   }<br />   for(i=0;i<n;i++)<br />   {<br />      contador = 0;<br />      if(flag[i]==-1){        <br />        dfs(i);<br />        maiorFamilia = (contador>maiorFamilia)?contador:maiorFamilia;<br />      }<br />   }<br />   printf("A maior familia possui %d pessoas.\n",maiorFamilia);      <br />   <br />return 0;<br />}