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:

Artigo: Capítulo 4.2 do livro Competitive Programming I

Ler das páginas 58 a 60 do livro.

Nota: Para quem não tem o livro

É normal que muitos não tenham uma cópia do livro. Felizmente a primeira edição do livro está disponível de graça neste link, a página 58 à 60 (ou da 70 à 72 do PDF).

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:

Artigo: Capítulo 4.3 do livro Competitive Programming I

Ler das páginas 67 a 68 do livro (ou 79 a 80 do PDF).

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:

Artigo: Capítulo 4.2 do livro Competitive Programming I

Ler das páginas 60 a 61 do livro (ou 72 a 73 do PDF).

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:

Artigo: Capítulo 4.3 do livro Competitive Programming I

Ler das páginas 68 a 69 do livro (ou 80 a 81 do PDF).

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:

Artigo: Capítulo 4.2 do livro Competitive Programming I

Ler das páginas 66 a 67 do livro (ou 78 a 79 do PDF).

* 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:

Artigo: Capítulo 4.2 do livro Competitive Programming I

Ler das páginas 65 a 66 do livro (ou 77 a 78 do PDF).

* 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:

Artigo: Capítulo 4.2 do livro Competitive Programming I

Ler das páginas 61 a 65 do livro (ou 73 a 77 do PDF).

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:

*Artigo: Slides de pesquisa em grafos

Um conjunto de slides que contém todos estes conceitos acompanhados de mais exemplos e melhores imagens.

*Artigo: Pesquisa em grafos do TopCoder

Um artigo sobre o tema que tem uma maior incidência na implementação.

Pesquisa em profundidade

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

Problema 1: Coast Length

Problema do Kattis, coast - Coast Length

Um problema mais interessante com grafos dirigidos.

Problema 2: Fox And Names

Problema A da ronda 290 (Div. 1) do CodeForces - Fox And Names

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

*Problema 3: Checkposts

Problema C da ronda 244 (Div. 2) do CodeForces - Checkposts

Pesquisa em largura

Vejamos um único problema que ilustra bem o conceito:

Problema 4: Breadth First Search: Shortest Reach

Problema do HackerRank, bfsshortreach - Breadth First Search: Shortest Reach

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:

*Problema 5: Theseus and labyrinth

Problema D da ronda 354 (Div. 2) do CodeForces - Theseus and labyrinth

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.