O mundo como grafo: redes, mapas e rotas

Grafos escondidos por toda parte

Uma vez que você aprende a estrutura, começa a ver grafos em quase tudo. A rede social é o exemplo mais óbvio: cada pessoa é um vértice, cada amizade é uma aresta não dirigida, cada seguida é uma aresta dirigida. Sugerir amigos é procurar vértices a dois passos de você no grafo, os amigos dos seus amigos. O mapa de trânsito é outro clássico: os cruzamentos viram vértices, as ruas viram arestas, e o peso de cada aresta é a distância ou o tempo. Achar o melhor caminho até um lugar é achar o menor caminho somando pesos nesse grafo, exatamente o que o aplicativo de rotas faz. A web inteira é um grafo gigante e dirigido: cada página é um vértice, cada link é uma aresta com sentido. Buscadores rankeiam páginas analisando esse grafo de links.

A lista não para nas redes visíveis. Rotas de entrega são grafos de endereços ligados por trajetos com peso. A malha de voos é um grafo de aeroportos e conexões. As dependências entre tarefas de um projeto formam um grafo dirigido: a tarefa B só começa depois da A, então há uma aresta de A para B, e organizar a ordem de execução é caminhar por esse grafo. Até a estrutura de pastas do computador, que você viu como árvore, é um caso de grafo. O ponto é que problemas que pareciam não ter nada em comum, sugerir amigos e traçar rotas e ordenar tarefas, viram o mesmo tipo de problema por baixo: caminhar por um grafo. Aprender a estrutura uma vez destrava todos eles.

Modelar é decidir vértice e aresta

Transformar um problema em grafo se resume a duas decisões. Primeira: o que é um vértice? Escolha as coisas que se relacionam, os itens que vão virar pontos. Segunda: o que é uma aresta? Escolha a relação entre pares dessas coisas que vale a pena representar. Feitas essas duas escolhas, o resto costuma seguir naturalmente, inclusive se o grafo é dirigido (a relação tem sentido?) e se tem peso (a relação tem um custo?). Num problema de amizades, vértice é pessoa e aresta é amizade, não dirigida e sem peso. Num problema de rotas, vértice é local e aresta é trajeto, com peso igual à distância. O segredo é que a mesma coisa pode virar vértice ou aresta dependendo da pergunta, então vale pensar no que você quer descobrir antes de fixar o modelo.

O mesmo problema, mil disfarces

Fecha o módulo uma ideia que se repetirá nos próximos: a maioria dos problemas de grafo é, no fundo, uma pergunta sobre caminhos. Dá para chegar daqui até lá? Qual o caminho mais curto? Quantos passos separam duas pessoas? Existe um ciclo? Essas perguntas aparecem disfarçadas de rota, de sugestão de amigo, de grau de separação, de ordem de tarefas, mas todas se respondem caminhando pelos vértices e arestas de um grafo. É por isso que o próximo módulo dedica-se aos percursos: as duas grandes formas de explorar um grafo passo a passo, a busca em largura e a busca em profundidade. Com o grafo modelado e uma dessas buscas na mão, uma quantidade enorme de problemas do mundo real passa a ter solução. Você já tem a estrutura; falta aprender a caminhar por ela.