Programando com Grafos - Revista easy Java Magazine 29

Imagine-se em um dia normal. Você resolve fazer uma pausa no trabalho, e vai dar uma olhada no Facebook. Ao lado do seu mural, estão oito solicitações para jogos, dois aniversários, e três “amigos recomendados”. Mas, como assim, “amigos recomendados”? Afinal, como o Facebook recomenda amigos? A resposta é: uma estrutura de dados chamada grafo.

As pessoas que você adicionou são organizadas em uma estrutura chamada grafo. Usando o grafo dos seus círculos sociais e dos seus amigos, o Facebook é capaz de determinar que outros usuários você pode conhecer. Isso porque grafos são estruturas que representam os relacionamentos entre objetos, e esses objetos podem ser tão diversos quanto cidades, times de futebol ou amigos de Facebook, por exemplo. Aliás, grafos descrevem não só amigos de Facebook, mas amigos de qualquer rede social.

Devido à importância dos grafos como estrutura de dados para aplicações computacionais, esse artigo visa apresentar uma breve introdução ao tema. Assim, nas próximas seções iremos mostrar um exemplo de um grafo de rede social, fornecendo maiores explicações de como os grafos podem ser representados tanto por diagramas quanto computacionalmente.

Uma breve história de grafos

O primeiro registro que se tem da ideia de grafos vem do conhecido matemático Leonhard Euler, em seu artigo “The solution of a problem relating to the geometry of position”, publicado em 1736. Esse artigo trata do problema das Pontes de Königsberg, ilustrado na Figura 1, no qual se deve atravessar as 7 pontes da cidade em uma caminhada contínua, passando por cada uma delas apenas uma vez. Talvez o leitor reconheça nesse problema certa semelhança com um problema clássico de xadrez, “A Viagem do Cavaleiro”, cuja solução pode ser vista na Figura 2. Esse problema foi desenvolvido pelos chineses e pelos árabes, e trata de uma situação na qual um cavaleiro deve percorrer todas as casas de um tabuleiro sem repetições. O cavaleiro quer evitar repetições porque ele consegue ver todos os pontos turísticos em uma só visita, e ele não gosta de perder tempo. Esse problema é muito similar ao posterior problema do Caixeiro-viajante, no qual se procura a melhor forma de passar por um número qualquer de cidades, sem passar em alguma mais de uma vez.

Figura 1. Ilustração do problema das Pontes de Königsberg (Fonte: Wikipédia).

O termo “grafo” surgiu pela primeira vez em 1878, em um artigo de James Joseph Sylvester, no qual ele propõe uma estrutura similar aos diagramas Kekulé, usados na química. Um dos primeiros programas a usar grafos foi escrito em 1969, por Heinrich Heesch. Ele publicou um método para resolver o Problema das Quatro Cores, que trata de colorir diferentes setores de um plano com quatro cores diferentes sem que duas áreas vizinhas tenham a mesma cor. Acredite, é mais complicado do que parece.

Figura 2. Uma solução para A Viagem do Cavaleiro em um tabuleiro 8x8 (Fonte: Wikipédia).

Descrição formal

Um grafo é, essencialmente, um diagrama composto por vértices (tipicamente representados por círculos ou retângulos) que podem ou não ser conectados por arestas (representadas por segmentos de retas ou arcos, com ou sem setas). Os vértices podem ser quaisquer entidades que possam estar relacionadas entre si. Nesse artigo, vamos usar grafos para representar relacionamentos de amizades entre usuários, como acontece no Facebook.

...