Algoritmos em grafos simples

Agora que já vimos como representar um grafo com código, neste artigo iremos ver os primeiros algoritmos em grafos, que servirão de base para muitos problemas. Veremos dois algoritmos base que serão importantes para muita da teoria que se seguirá. Posteriormente, olharemos para alguns outros algoritmos que usam como primitiva um dos dois anteriores.

As duas últimas secções são opcionais por serem um pouco mais complicadas, mas quem perceber bem os restantes tópicos consegue segui-los facilmente.

Pesquisa em profundidade

Este primeiro algoritmo é um algoritmo de pesquisa num grafo, ou seja, um algoritmo que permite percorrer um grafo. Para tal vamos começar com um capítulo do livro do costume:

Notem ainda que só indicamos as primeiras páginas do capítulo. As seguintes contêm os conceitos que falamos a seguir.

Pesquisa em largura

Seguimos com o equivalente para pesquisa em largura:

Componentes conexos de Flood Fill

A primeira aplicação destes algoritmos será determinar as componentes conexas de um grafo não direcionado. Uma componente conexa é um conjunto maximal de nós que é conexo, ou seja, um conjunto ao qual se adicionarmos um qualquer nó, deixa de ser conexo. Conexo neste contexto significa que existe um caminho entre quaisquer dois nós.

Tanto a pesquisa em profundidade como a pesquisa em largura podem ser usadas para este propósito, mas normalmente usa-se a pesquisa em profundidade por poupar mais memória e por ser mais simples de implementar. Este método normalmente chama-se flood fill. Vamos ver mais sobre ele:

Distâncias mínimas em grafos sem pesos

Passamos agora a uma aplicação típica e muito útil da pesquisa em largura. Se estivermos num grafo sem pesos, então a distância entre dois nós é simplesmente o número de arestas do caminho com o mínimo de arestas entre os dois nós. Mas se pensarmos bem, a pesquisa em largura itera nos nós na ordem de distância dos nós iniciais. Assim, podemos usar essa pesquisa para determinar distâncias. Vejamos como:

Esta secção do livro é um pouco mais incompleta, por isso recomendamos que consultem algum do material extra referido na secção aplicações.

Ordenação topológica

Este tema é um pouco diferente e aplica-se a uma classe em particular de grafos, nomeadamente Directed Acyclic Graphs, ou DAGs ("grafos direcionados sem ciclos"). Nestes grafos, como o nome indica, não há ciclos, logo é possível explorar o grafo de forma diferente. Por exemplo, é possível obter uma ordem dos nós tal que se um nó $a$ está antes de outro $b$ na ordem, então não há nenhum caminho de $b$ para $a$. Se pensarmos neste grafo como um grafo de precedências, por exemplo, pre-requisitos de disciplinas ou cadeiras (para ter Literatura II é preciso já ter tido Português I e Literatura I, por exemplo), esta ordem dá-nos uma forma de fazer as disciplinas/cadeiras sem violar as restrições de precedência. Outra propriedade que estes grafos têm que veremos mais tarde é que é possível aplicar programação dinâmica facilmente, exatamente por não existirem ciclos, mas veremos isso noutro artigo.

Vejamos então o que nos diz o livro sobre isto:

* Componentes Fortemente Conexos

Já vimos componentes conexas em grafos não dirigidos, agora a pergunta é: e para grafos dirigidos? Podemos pensar num conceitos semelhante e considerar que dois nós $a$ e $b$ estão na mesma componente conexa se existir um caminho de $a$ para $b$ ou de $b$ para $a$, e temos uma noção semelhante há que já tínhamos visto. Porém, uma noção mais útil, é a de componentes fortemente conexas, onde dois nós $a$ e $b$ estão na mesma componente conexa se existir um caminho de $a$ para $b$ e de $b$ para $a$. Esta subtil mudança de "ou" para "e" parece trivial, mas implica muita coisa.

O livro indica-nos o caminho:

* Pontos de Articulação e Pontes

Finalmente, o último conceito que iremos ver, são pontos de articulação e pontes (dois conceitos análogos). Pensemos num grafo não dirigido qualquer. Alguns vértices podem ser mais importantes que outros, estruturalmente falando. Por exemplo, se ao remover um determinado vértice, o grafo passar a ser desconexo, então esse vértice tem alguma importância. A um vértice com esta propriedade chamamos ponto de articulação. O mesmo pode ser dito sobre uma aresta e nesse caso chamamos-lhe ponte.

Vejamos como calcular estas duas noções:

Aplicações

Colocámos alguns problemas à parte porque os vários conceitos misturam-se. Assim veremos alguns problemas mais para aplicar algoritmos de pesquisa em profundidade e outros para pesquisa em largura.

Mas antes de irmos aos problemas, aqui têm algum material extra para verem os conceitos falados de outra forma e com outros detalhes:

Pesquisa em profundidade

Vamos começar com um problema mesmo simples só para aplicar o conceito base (com o objetivo de calcular componentes conexas).

Um problema mais interessante com grafos dirigidos.

Finalmente, mais um problema apenas para implementação de componentes fortemente conexas.

Pesquisa em largura

Vejamos um único problema que ilustra bem o conceito:

Nota: este problema poderá dar um pouco mais trabalho de implementação, apesar de ser simples, se quiserem algo mais simples tentem o próximo:

Conclusão

Para terminar, é importante notar que o objetivo destes conceitos todos é serem usados como primitivas para calcular outras propriedades de grafos úteis para um problema. Vimos muitas aplicações possíveis de várias naturezas, mas é importante lembrar que há muitas outras coisas que se podem fazer. Algumas delas veremos nos próximos artigos (por exemplo, propriedades de grafos especiais, como de árvores, DAGs ou de grafos bipartidos), mas também outras coisas mais específicas como caminhos Hamiltonianos e Eulerianos.