Olá, caro Deviante! Tudo bem por aí?

Poucas estruturas são tão versáteis quanto os Grafos para encontrar correlações entre fatos distintos.

Para pesquisar informações armazenadas em um grafo, utilizamos algoritmos de travessia. O de Busca por Largura  (Breadth-First Search — BFS em inglês) é um dos mais populares.

Ele explora os vértices nível por nível, começando por uma origem e avançando gradualmente para os níveis seguintes.

Explicarei abaixo de forma resumida como esse algoritmo funciona e mostrarei como ele poderia ajudar um computador a localizar as seleções eliminadas nas quartas de final da Copa do Mundo de 2022.

Curioso? Bora entender como tudo isso funciona!

Introdução

Precisamos projetar um sistema que armazene, em um grafo direcionado, informações sobre a Copa do Mundo de 2022. Para simplificar o entendimento, vamos utilizar apenas as partidas ocorridas a partir das quartas de final.

Lista de Adjacências

O primeiro passo para executar nosso algoritmo será o de preencher a lista de adjacências que irá basear nosso grafo. Como ele não possui ciclos e é direcionado, esta lista será um pouco mais simples:

• Quartas de Final → Brasil x Croácia → Vencedor (Croácia)
• Quartas de Final → Brasil x Croácia → Eliminado (Brasil)
• Quartas de Final → Holanda x Argentina → Vencedor (Argentina)
• Quartas de Final → Holanda x Argentina → Eliminado (Holanda)
• Quartas de Final → Inglaterra x França → Vencedor (França)
• Quartas de Final → Inglaterra x França → Eliminado (Inglaterra)
• Quartas de Final → Marrocos x Portugal → Vencedor (Marrocos)
• Quartas de Final → Marrocos x Portugal → Eliminado (Portugal)

Basicamente, temos um vértice inicial denominado Quartas de Final e seus vértices filhos representam as partidas. Cada partida, por sua vez, possui dois vértices descendentes: um para a seleção vencedora e outro para a seleção eliminada.

As Propriedades dos Vértices

Na implementação clássica da BFS, cada vértice possui três propriedades importantes:

• Cor: indica o estado do vértice durante a execução do algoritmo.
• Distância: quantas arestas existem entre o vértice atual e o vértice inicial.
• Vértice-pai: registra qual vértice levou à descoberta do vértice atual.

Antes do início da busca, todos os vértices iniciam com valores básicos:

• Cor: branca
• Distância: infinita
• Vértice-pai: nulo

Iniciando a Busca

Após preencher a lista de adjacências, podemos iniciar a execução da BFS. Em sua implementação clássica, o algoritmo utiliza dois recursos principais:

1. O atributo cor, presente em todos os vértices.
2. Uma estrutura de dados do tipo fila, responsável por armazenar temporariamente os vértices descobertos.

Em nossa implementação, as cores possuem os seguintes significados:

• Branco: não visitado.
• Cinza: vértices descobertos
• Azul: completamente processado (na literatura a cor padrão é o preto).

O funcionamento geral do BFS é o seguinte:

• Insere o vértice inicial na fila.
• Remove da fila e o define como vértice-pai.
• Todos os seus vizinhos ainda não visitados (cor branca) são:
  • Marcados com a cor cinza;
  • Recebem sua distância em relação ao vértice inicial;
  • Recebem um vértice-pai;
  • Entram na fila.
• Depois de analisar todos os vizinhos, marca o vértice atual com a cor azul.
• O processo continua até que a fila esteja vazia.

Voltando ao Exemplo

Vamos acompanhar a execução da BFS em nosso grafo da Copa do Mundo.

Inicialmente, a fila contém apenas o vértice Quartas de Final.

Figura 1: Diagrama de estados, desenhado de forma manual, que mostra os estados de preenchimento do Grafo descritos ao longo do texto.

A primeira varredura remove o vértice da fila e o processa. As etapas seguintes descobrem os vértices correspondentes às partidas, os colorem com a cor cinza e os inserem na fila.

Após a análise de todos os seus descendentes, o vértice Quartas de Final é marcado com a cor azul.

Nesse momento, a fila contém:

• Brasil x Croácia
• Holanda x Argentina
• Inglaterra x França
• Marrocos x Portugal

Observe que todos esses vértices estão exatamente à mesma distância do vértice inicial: uma aresta.  A Busca por Largura percorre o grafo em “camadas“, explorando primeiro todos os vértices de um mesmo nível antes de avançar para o próximo.

Descendo um Nível

No segundo nível, o vértice Brasil x Croácia é removido da fila e processado. Os vértices vencedor (Croácia) e eliminado (Brasil) são descobertos, recebem a cor cinza, têm sua distância definida com 2 em relação ao vértice inicial e são inseridos na fila.

Figura 2: Descrição do preenchimento da segunda etapa do Algoritmo BFS.

O mesmo procedimento é repetido para as demais partidas. Ao final desse processo, todos os vértices que representam vencedores e eliminados estarão armazenados na fila.

Como esses vértices não possuem descendentes, eles serão processados, marcados com a cor azul e removidos da fila. E, quando a fila estiver vazia, a execução da BFS estará concluída.

Conclusão

Importante ressaltar que este exercício possui caráter puramente didático e foi elaborado para demonstrar como a Busca por Largura funciona.

Partimos de uma estrutura simples de relacionamentos para construir um grafo organizado em níveis. A partir dele, conseguimos percorrer sistematicamente todas as informações armazenadas.

À primeira vista, utilizar a BFS para identificar eliminados em quartas de final pode parecer muito esforço para pouco resultado. Porém, tudo muda quando, por exemplo, o grafo contém milhões de usuários de uma rede social.

Figura 3: Exemplo de um grafo complexo com milhares de vértices e arestas para serem explorados.

Nesses casos, algoritmos como a Busca por Largura tornam-se indispensáveis.

Espero que este artigo tenha lhe ajudado. Muito obrigado pela leitura e fique à vontade para continuarmos a conversa nos comentários!