Artigos Canal Mais Programando com Grafos - Revista easy Java Magazine 29
Artigo do tipo Tutorial
Recursos especiais neste artigo:
Conteúdo sobre boas práticas
Autores: Dante Moreira Zaupa e Patrícia Jaques Maillard
Programando com Grafos
Este artigo apresenta uma introdução à teoria de grafos. Um grafo é um tipo abstrato de dados, assim como listas, pilhas e filas, que permite representar relações binárias entre dois objetos. Em um grafo, os objetos são representados por nodos (também chamados de vértices) e as relações entre dois objetos por uma aresta. Embora o grafo seja um dos mais importantes tipos de dados da computação, a API padrão da JDK (até a presente versão – 7) não apresenta uma implementação disponível para ele. Dessa forma, esse artigo visa apresentar uma visão prática de grafos, mostrando as representações existentes mais utilizadas, e fornecendo ao leitor diretrizes para a escolha da melhor representação para sua aplicação.

Em que situação o tema útil
Grafos são úteis para representar relações entre diferentes elementos. Um grafo pode ser empregado, por exemplo, para representar as relações entre usuários de uma aplicação de rede social, como o Facebook. Nesse caso, os nodos do grafo representam pessoas, uma ligação entre dois nodos (aresta) significa uma relação entre elas, que poderia ser classificada em uma ou mais categorias (ou seja, um amigo, ou um colega, ou um conhecido). Um grafo poderia também ser empregado para representar uma malha aérea. Os aeroportos são os vértices do grafo e cada voo é representado por uma aresta, que poderia ter um peso para sinalizar a distância em quilômetros daquele trecho aéreo. Como abstração, grafos são bastante flexíveis, capazes de expressar desde relações binárias simples (ou seja, uma ligação que pode existir ou não, como no caso da existência de uma amizade entre duas pessoas em uma rede social), quanto relações mais complexas, como, por exemplo, a distância entre duas paradas para um trecho de linha de ônibus.

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.

...

Quer ler esse conteúdo completo? Tenha acesso completo