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:

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 “nó“) é 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:

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:

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:

Resolvendo problemas – Algoritmos comuns

Flood Fill

Geralmente estes problemas são muito simples de perceber, e mais ainda de implementar.

Vejamos um exemplo:

Num país distante, um terramoto destruiu uma grande parte das estradas que ligavam as suas cidades. Assim, certas zonas ficaram sem qualquer meio de contactar com outras. O nosso objectivo é saber quantas destas zonas é que existem. Uma zona é definida como sendo uma ou mais cidades, sem qualquer ligação ao exterior.

Sem grandes esforços, podemos chegar a um algoritmo simples:

• Precisamos de um vector que nos diga, num dado instante, se o elemento i foi ou não visitado (inicialmente todos os elementos começam a 0 (não visitado).
• Começando no primeiro elemento, marcar todos os elementos que lhe estão ligados como visitados. E todos os que estão ligados a esses (que ainda não foram marcados, obviamente) também. E por aí fora.
• Se quando chegarmos ao fim ainda houver elementos por marcar, então estamos perante a existência um novo centro urbano.

Um flood fill pode ser feito basicamente de 2 maneiras: em profundidade (DFS – depth-first search) ou em largura (BFS – breadth-first search) (simplificando, pois existem mais alternativas como o “DFS with iterative deepening” ou “breadth-first scanning“).

Breadth-first search

Podemos ver a pesquisa em largura como uma torneira aberta num chão de tijoleira: a primeira a ser molhada é a que se encontra no local onde está a torneira. Todas as que estão à volta serão as próximas, e por aí em diante, numa expansão a partir de um dado centro.

Este algoritmo normalmente não levanta muitos problemas a implementar, quer iterativa quer recursivamente: temos o nosso vector de elementos visitados (e por visitar) e uma lista dos elementos que acabaram de ser visitados (recentemente). Para cada um destes últimos, adicionamos a uma nova lista os seus vizinhos ainda não visitados. Depois de termos feito isto com todos os elementos, passamos para a nova lista (e podemos esquecer a antiga).

Depth-first search

Os algoritmos de pesquisa em profundidade normalmente são mais complicados de compreender, porque dão trabalho a implementar iterativamente e muita gente não está familiarizada com a recursividade. Contudo, após esse problema estar ultrapassado, é ainda mais fácil de implementar do que o BFS.

Vamos ver o DFS como um rato à procura de um queijo perdido num labirinto: ele escolhe um caminho, e mal encontra um beco sem saída volta para trás e vira pelo primeiro caminho ainda não pesquisado. É exactamente este funcionamento que vamos implementar, desta vez em pseudo-código.

Partindo do vértice inicial, v.

função dfs(v)
  marcar v como visitado
  para todos os vértices i adjacentes a v
    se i não tiver sido visitado
      dfs(i)

Problemas modelo

Street Race (International Olympiads in Informatics 95)

Dados: um grafo direccionado, um ponto inicial e um ponto final.

Encontrar todos os pontos p que um caminho do ponto inicial para o ponto final deve atravessar obrigatoriamente.

Análise: O algoritmo mais simples é remover cada ponto e verificar se o ponto final ainda é alcançado a partir do ponto inicial.

Fazendo um Flood Fill no ponto de partida, verificamos se o ponto de chegada foi ou não marcado como visitado (repetimos este procedimento removendo sempre um ponto de cada vez).

The Castle (International Olympiads in Informatics 94)

Dados: um mapa de um castelo (uma matriz) onde # representa uma parede e . uma casa em branco.

Descobrir qual o tamanho da maior sala do castelo, após deitar abaixo uma das paredes.

Análise: Ao ser fornecida a matriz temos uma representação implícita do grafo, cada casa sendo um vértice. Não precisamos de a transformar numa matriz/lista de adjacência, podemos usá-la para saber quais os vértices adjacentes.

Mais uma vez, deitamos uma parede abaixo e verificamos o tamanho da maior sala (através de um Flood Fill e contando quantos quadrados foram visitados).

Fontes

1. Wikipedia: https://en.wikipedia.org/
2. USACO Training Program: http://train.usaco.org