O que é um grafo e para o que serve
Meu primeiro contato com grafos foi na época da faculdade e me gerou um certo desespero. Aqueles conceitos, definições e notações matemáticas não faziam sentido nenhum e pareciam um assunto de outra realidade. Depois de aprender da maneira mais difícil, eu comecei a utilizar grafos em aplicações práticas. Foi a partir desse momento que todas aquelas definições confusas foram substituídas por noções intuitivas e simples. E é sobre isso que eu quero falar aqui.
Imagine uma rede social (seu instagram, por exemplo). Ela possui diversos usuários, inclusive você. Os usuários dessa rede social interagem entre si de diversas formas, seja através de curtidas, comentários ou o simples ato de seguir. Essas interações são responsáveis por estabelecer as conexões entre os usuários.
A imagem abaixo representa justamente isso. Cada círculo representa um usuário, de forma que temos o usuário 1, usuário 2, ..., até o usuário 6. Esses usuários possuem algo tipo de conexão entre si. O usuário 1 possui uma conexão com o usuário 2 e o usuário 5. O usuário 6 possui uma conexão somente com o usuário 4, e por aí vai.
Fez sentido? Isso é um grafo. Um grafo nada mais é do que uma forma de representar dados. Formalmente, um grafo é formado por um conjunto de vértices (no caso do exemplo, os vértices são os usuários - ou as bolinhas) e um conjunto de arestas (no caso do exemplo, as arestas são as conexões existentes entre um usuário - ou aquelas linhas que conectam as bolinhas).
Vou te mostrar uma definição formal de grafo pra te assustar e depois vamos traduzir.
Um grafo G = (V,E) é um conjunto não-vazio de vértices V e um conjunto E de arestas. Uma aresta é um par não-ordenado (vi,vj), onde vi e vj são elementos de V.
Ainda parece confuso? Vamos traduzir!
Um grafo é uma coisa que tem pelo menos uma bolinha (vértice) e algumas retas ligando as bolinhas (arestas). Essas retas possuem duas pontas e cada ponta está ligada em uma bolinha.
Assim como essa definição, todas as outras que parecem complexas e confusas podem ser traduzidas para uma forma mais informal e intuitiva que faça mais sentido.
Mas... pra que serve tudo isso? Grafos são usados para resolver diversos problemas que vão desde a identificação da rota mais curta entre dois locais até sistemas de recomendações complexos como os utilizados pela netflix ou spotify.
No Google Maps, por exemplo, cada localização pode ser vista como um vértice e as estradas como as arestas. Nesse contexto, identificar a melhor rota entre dois destinos pode ser interpretado como um problema de identificar o melhor caminho entre dois vértices do grafo.
Em algum próximo post venho apresentar algumas aplicações interessantes utilizando grafos :)