2 - Como representar grafos no computador

Existem duas abordagens clássicas para implementar um grafo para uso nos algoritmos: como uma matriz de adjacência (ou vizinhança) ou uma lista de adjacência (ou vizinhos). Você vai ver as duas formas e em que momento seria mais vantajoso usar cada uma delas. Os critérios utilizados para diferenciar as formas de representação serão memória necessária para armazenar o grafo versus velocidade de acesso à informação.

Conheça agora os candidatos!

2.1 - Matriz de Adjacência

Essa é, para mim, a forma mais intuitiva de representar um grafo computacionalmente. A ideia é montar uma grande matriz, onde as linhas e colunas representarão os vértices do grafo, como se estivesse fazendo um cruzamento de todos os vértices. Nesse caso, cada posição da matriz representará uma aresta que liga o elemento da linha X com o elemento da coluna Y.

Veja um exemplo ilustrado no Quadro 01 para entender melhor. Abaixo segue a matriz de adjacência para o grafo do RN, apresentado no começo da aula:

Dessa forma, se quiser consultar qual o custo de ir de Santa Cruz até Mossoró (diretamente), basta consultar o Quadro 01 acima! Alguns detalhes: o custo de ir de uma cidade para ela mesma é zero (não gasta nada). Estou descartando qualquer custo de deslocamento interno no grafo. Outra coisa interessante na quadro é o valor de -1 que apareceu entre Pau dos Ferros e Santa Cruz. Isso acontece porque não existe ligação direta entre as duas cidades, e é impossível ir de uma para outra sem passar por outra cidade primeiro! Como -1 é um valor impossível em reais (claramente, o pessoal que inventou grafos nunca viu minha conta do banco ), coloquei para representar um peso infinito! Sacaram a estratégia?

As principais vantagens dessa representação é que as linguagens de programação normalmente possuem um tipo de matriz disponível para implementação, e o acesso ao valor de qualquer aresta é muito rápido (basta olhar a posição da matriz na linha e coluna desejada!).

Então se é tão bom, não precisava ter inventado outras formas de armazenar um grafo né?

Precisava...

Infelizmente, a representação por matriz é desvantajosa em algumas situações:

• Grafos com um número de nós muito grande vão exigir uma matriz enorme para representar. Imagina o gráfico de relações no Facebook para ele ficar lhe sugerindo amiguinhos: seria necessária uma grande quantidade de memória para armazenar a matriz, e seu programa ia começar a precisar de alguns pentes extra de memória RAM para rodar;
• Grafos com muitos vértices e poucas ligações, denominados grafos esparsos, teriam muitas casas da matriz armazenando um valor que indica que não há ligação (no nosso exemplo, o -1). Nesse caso, ocorreria muito desperdício de memória para representar poucos dados!

Então essa é uma ótima opção quando:

• O conjunto de vértices é pequeno ou médio;
• O grafo é bem preenchido (muitas ligações entre os nós).

E quando não se tem um grafo desses em mãos? Veja a segunda opção!

2.2 - Lista de Adjacência

A segunda forma de representação utiliza uma estrutura de dados clássica da computação para montar o grafo: uma lista ou lista ligada. Mas o que danado é isso?

Lembra que lá em programação estruturada você estudou os arranjos, especificamente vetores e matrizes (se não lembra, pelo amor de Deus dê uma olhadinha lá!)? Então, essas estruturas de dados são ditas sequenciais porque elas são armazenadas de forma sequencial. O que isso significa é que o computador vai deixar tudo juntinho na memória! Veja a Figura 06.

Foi como um exemplo visual para refrescar bem a sua memória!

Assuma que cada posição de memória possui 4 bytes (o suficiente para armazenar um valor do tipo inteiro). Como existiam quatro posições consecutivas livres, o vetor foi alocado com sucesso. Agora se o cenário fosse o seguinte:

Opa! Mesmo que a quantidade de memória livre seja a mesma (6 espaços nos dois cenários), no segundo não existe a quantidade necessária de casas em sequência para armazenar o vetor, logo o seu programa não vai conseguir executar a operação (provavelmente vai vir aquele Segmentation Fault ou Null Pointer Exception).

É normal que, com o tempo de uso, abrindo e fechando programas, e executando milhões de operações, a memória do seu computador comece a ficar fragmentada. E você viu lá em Arquitetura de Computadores e SO: quando acaba a memória, vem a danada da memória virtual (que usa o disco rígido), cai o desempenho da máquina e os usuários choram de dor e xingam nossos familiares… Para evitar que isso ocorra, foram idealizadas estruturas de dados que armazenam o dado de forma não-sequencial. Basicamente, elas guardam duas informações: o próprio valor que se quer armazenar, e onde o próximo valor da sequência está guardado na memória!

Professor, isso parece que dá trabalho de fazer!

Relaxe! Hoje em dia quase todas as linguagens possuem um tipo lista embutidas, ou uma implementação já pronta que você pode usar. Assim como as pilhas e filas, as listas podem ser utilizadas pelo elemento List do C#, então você só precisa entender como ela funciona, ok?

O resumo da ópera é: uma lista parece com um vetor, só que ela é armazenada de forma não-sequencial na memória. Qual a diferença então? É só performance: como a lista tem de descobrir a cada elemento onde está o próximo dela na memória, ela demora um pouquinho mais para executar do que o vetor. Mas essa diferença só vai ser sentida se for uma sequência muito grande de operações, então você pode utilizá-la a vontade para os exemplos daqui!

Agora que você tem uma noção do que é uma lista, vou lhe explicar o que é uma lista de adjacência! Uma lista de adjacência é… um vetor contendo todos vértices do grafo, onde cada posição será uma lista com os vizinhos daquele vértice! Observe a Figura 09 para clarear um pouco a explicação.

Nesse caso, o que você vai ter é um vetor de listas, onde cada lista contém apenas os vértices e o valor da aresta que o liga ao elemento correspondente do vetor. Essa abordagem é ótima para grafos esparsos ou com uma grande quantidade de vértices porque você só vai criar o que realmente existe, porém o tempo de acesso é mais demorado: para cada vértice inicial da aresta você vai ter de usar um laço de repetição para percorrer a lista até achar o nó de destino que você deseja (caso ele exista! Se não tiver uma ligação, você vai varrer a lista toda até descobrir isso ).

Como você pode ver, são estratégias de armazenamento de grafos para situações complementares, então dependendo da estrutura do seu grafo, você pode escolher aquela que será mais adequada para representá-lo no computador.

Até aqui foram apresentados o que é um grafo e como se pode representá-lo em um algoritmo de computador. Eu sei que ficou uma aula super teórica, mas nas próximas duas aulas você vai ver vários algoritmos que fazem percursos e caminhos em cima dessa estrutura. Então dê uma boa revisada e,, caso tenha dúvidas, não hesite de atacar os fóruns com uma chuva de perguntas.