Tipos de grafo: dirigido, não dirigido e com peso

Mão dupla ou mão única

A primeira grande escolha ao modelar um grafo é a direção. Num grafo não dirigido, a aresta é uma mão dupla: se existe ligação entre A e B, ela serve para ir de A a B e de B a A, sem distinção. É o modelo natural para relações simétricas, aquelas que valem igual nos dois lados. Amizade no sentido clássico é assim: se você é meu amigo, eu sou seu amigo. Uma estrada de mão dupla entre duas cidades também. No desenho, essas arestas são traços simples, sem ponta de seta.

Já num grafo dirigido, cada aresta tem um sentido, marcado por uma seta. A ligação vale só na direção da seta. De A para B não garante nada de B para A. Esse tipo modela relações de mão única. Numa rede social onde você segue perfis, seguir é dirigido: você pode seguir uma celebridade sem que ela siga você de volta. Uma rua de sentido único é dirigida: dá para descer, não dá para subir. Links entre páginas da web também são dirigidos: um site aponta para outro, e o outro pode não retribuir. Escolher entre dirigido e não dirigido não é detalhe estético, muda quais caminhos existem no grafo.

Arestas que carregam um número: o peso

A segunda escolha é sobre o peso. Num grafo sem peso, uma aresta só diz se há ou não há ligação, como um interruptor: ligado ou desligado. Isso basta para perguntas do tipo dá para chegar de A a B? Mas muitas vezes a ligação tem um custo, e aí entra o peso: um número colado na aresta. Num mapa de estradas, o peso pode ser a distância em quilômetros; num grafo de voos, o preço da passagem; numa rede de computadores, o tempo de resposta. Com pesos, a pergunta fica mais rica: não é só se existe caminho, mas qual o caminho mais barato, mais curto ou mais rápido. Esse tipo de pergunta é o coração de aplicativos de rota, que buscam o menor caminho somando pesos.

Escolher o tipo certo antes de programar

As duas escolhas, direção e peso, se combinam livremente e dão quatro sabores de grafo: não dirigido sem peso, não dirigido com peso, dirigido sem peso e dirigido com peso. Antes de escrever qualquer linha, vale parar e responder duas perguntas sobre o problema. A relação vale nos dois sentidos ou tem direção? Cada ligação tem um custo que importa ou basta saber se existe? As respostas fixam o tipo de grafo e, com ele, o que o programa vai conseguir responder. Modelar um mapa de metrô para saber se dá para ir de uma estação a outra pede um grafo não dirigido sem peso. Modelar o mesmo metrô para achar a rota mais rápida pede peso (o tempo entre estações). Errar o tipo no começo custa caro depois.