Grafos – 1ª Parte

Introdução: O que é um grafo

O leitor certamente que já ouviu falar em grafos. São amplamente usados em matemática, mas sobretudo em programação.

Formalmente, um grafo é uma colecção de vértices (V) e uma colecção de arcos (E) constituídos por pares de vértices. É uma estrutura usada para representar um modelo em que existem relações entre os objectos de uma certa colecção.

Pense nos vértices como “locais“. O conjunto dos vértices é o conjunto de todos os locais possíveis. Nesta analogia, os arcos (ou arestas) representam caminhos entre estes locais. O conjunto E (vou usar o termo mais comum – “E” do inglês “edges“) contém todas as ligações entre os locais.

Utilizar grafos é de grande utilidade na representação de problemas da vida real.

Podem ser cidades, e uma rede de estradas. Redes de computadores. Até mesmo os movimentos de um cavalo num tabuleiro de xadrez podem ser representados através de um grafo. Na prática:

  • As linhas de metro das grandes cidades utilizam grafos de modo a minimizarem o tempo das ligações;
  • A distribuição de correio, minimizando percursos de forma a optimizar as deslocações, tanto para um único carteiro como para uma equipa (o mesmo se aplica a empresas de distribuição);
  • Os sistemas de patrulha da PSP permitem estudos de optimização recorrendo a grafos.

E depois de representá-los correctamente, o que podemos descobrir? O caminho mais curto entre duas cidades num mapa; dadas as coordenadas de n cidades, que estradas construir de modo que o número de quilómetros de estrada seja mínimo mas fiquem todas conectadas; dado um mapa de uma casa (em que paredes e chão são representados com caracteres diferentes) saber qual a divisão com maior área; etc.

As possibilidades são grandes, e ficarão admirados com a facilidade com que estes problemas são resolvidos.

Representação

Graficamente, um grafo é normalmente representado da seguinte forma:

Grafo: exemplo 1 Grafo: exemplo 2

Vértices são pontos ou círculos; arcos são linhas entre eles.

Usando o primeiro exemplo, V = {1, 2, 3, 4, 5, 6} e E = {(1,3), (1,6), (2,5), (3,4), (3,6)}.

Cada vértice (também chamado ““) é um membro do conjunto V. Cada arco é um membro do conjunto E.

Terminologia

Como é de esperar, tendo aplicações tão variadas, o grafo adapta-se às nossas necessidades. Assim, existem vários tipos de grafos. Aliados a isso, existem termos comummente usados para descrever um grafo, ou parte dele. Vou listar alguns (entre eles os mais comuns):

Vértice isolado
Um vértice é considerado isolado se não possuir nenhuma ligação a outro vértice (bastante óbvio).
Grafo trivial (ou ponto)
Grafo sem arestas e um único nó.
Laço (ou loop/self-loop)
Um arco é um laço se em ambas as extremidades estiver o mesmo vértice (nenhum dos grafos apresentados possui laços).
Grafo simples
Um grafo é simples se não contiver laços nem arcos repetidos em E.
Vértices adjacentes
Dois vértices (u e v) são adjacentes se existir um arco que possui uma extremidade em u e outra em v. Os vizinhos de um vértice são todos os vértices adjacentes a ele.
Grafo pesado (ou grafo de arcos pesados)
A cada aresta está associado um valor. Pode ser uma distância, um custo, seja o que for.

Uma definição similar existe para grafo de nós pesados.

Grau de um vértice(ou valência)
O grau de um vértice é o número de arcos que lhe são incidentes. Um arco (u,v) é incidente tanto no vértice u como no vértice v.

Pode-se distinguir grau de entrada e grau de saída em grafos direccionados (ver à frente).

Grafo direccionado
Cada arco tem um nó de origem e um nó de chegada. O exemplo típico é o das redes de estradas, uma vez que existem estradas só com um sentido seria o caos se um GPS não soubesse distingui-las.

Para os representar, são desenhados com setas para representar a direcção:

Grafo: exemplo 3 (direccionado)Da teoria para a prática

Certamente que tudo o que foi demonstrado até agora é muito bonito, mas o que interessa ao leitor é saber como transformar aqueles desenhos e aquelas setas em algo que o seu programa possa interpretar.

Existem diversas formas de os armazenar, umas que ocupam mais espaço em memória mas mais eficientes, outras que ocupam menos espaço, são mais eficientes mas mais difíceis de programar. Vou somente falar das mais habituais.

Matriz de adjacência

Esta é uma representação bastante fácil de programar, mas bastante pouco eficiente em termos de memória.

Consiste uma matriz N x N (onde N é um número de vértices) onde (i,j) indica se existe uma ligação do vértice i para o vértice j. Alternativamente, pode representar o tamanho dessa ligação.

Vantagens:

  • Fácil de programar.
  • Pode representar um grafo pesado sem comprometer a complexidade.
  • Caso o grafo não seja pesado e seja possível existir mais do que uma ligação entre dois vértices, (i,j) pode representar o número de ligações entre eles.
  • Verificar se dois vértices são adjacentes é muito rápido, tal como adicionar ou remover ligações.

Desvantagens:

  • Elevado desperdício de memória (especialmente se o grafo for disperso).
  • Debugging é difícil, uma vez que a matriz tende a ser grande.
  • Listar todas as arestas incidentes num dado vértice é demorado (força-nos a percorrer todos os vértices).

Como exemplo, o primeiro grafo apresentado teria este aspecto:

  V1 V2 V3 V4 V5 V6
V1 0 0 1 0 0 1
V2 0 0 0 0 1 0
V3 1 0 0 1 0 1
V4 0 0 1 0 0 0
V5 0 1 0 0 0 0
V6 1 0 1 0 0 0

Listas de adjacência

Nesta representação limitamos-nos a guardar a informação de todas as arestas incidentes num dado vértice.

Isto pode ser feito usando um vector de tamanho V (número de vértices), onde v[ i ] guardará a lista dos arcos ou vértices conectados ao vértice i.

A maneira de guardar estes vértices/arcos varia, dependendo da linguagem, podendo-se usar listas encadeadas ou mesmo transformar o vector numa matriz.

Vantagens:

  • Listar todas as arestas incidentes num dado vértice é fácil (a operação mais frequente na maioria dos algoritmos).
  • Baixo desperdício de memória.

Desvantagens:

  • Dependendo da implementação, difícil de programar.
  • Representar um grafo pesado implica uma matriz de estruturas ou mais um campo na lista encadeada.
  • Para verificar se dois vértices são adjacentes necessitamos de percorrer todos os vértices adjacentes a um deles.

Mais uma vez, o primeiro grafo fornecido poderia ser representado desta forma:

Vértice Vértices Adjacentes
1 3, 6
2 5
3 1, 4, 6
4 3
5 2
6 1, 3

Publicado na edição 10 (PDF) da Revista PROGRAMAR.