O Facebook possui mais de 1 bilhão de usuários em sua plataforma. E para gerir tudo isso, é necessário um algoritmo inteligente e eficaz. Logo, para a empresa conseguir lidar com os relacionamentos entre usuários, foi adotado uma estrutura matemática e computacional chamada Grafo.
O que é Grafo?
É uma estrutura para modelar conjuntos de objetos que tenham relacionamentos entre si. Essas interações entre objetos são representados por arestas.
Os Grafos podem ser usados para resolver diversos problemas de relacionamento entre grandes conjuntos de dados, de modo que retorne alguma informação útil.
representando grafos
A imagem acima é um exemplo de grafo não direcionado e cada vértice e aresta podem carregar algum tipo de dado.
Quais são os dados que os Grafos podem oferecer?
Isso depende da implementação e da finalidade. Em uma rede social, por exemplo, os vértices podem representar cada usuário e as arestas representar as suas amizades.
Na imagem já apresentada, Leonardo tem amizade com Laís e Julio, mas Leonardo não tem amizade com Bruna. Como Laís e Julio têm amizade com Bruna, então ela e Leonardo têm amigos em comum, logo a rede social pode recomendar a amizade entre esses dois usuários.
Desse modo, para o objetivo citado, o grafo ajuda a manter e criar novas relações na rede social, o que é fundamental para esse modelo de negócio. Agora já podemos ter uma ideia de como é feito os relacionamentos entre usuários do Facebook.
Por que usar Grafos?
Como já dito anteriormente, se seu problema envolve múltiplos relacionamentos entre informações, então grafos é uma alternativa para você. Pois, essa estrutura permite um alto poder de abstração entre correlação de vértices. E possuir uma estrutura fundamentada lhe permite acessar gigantescas quantidades de dados, o que é de suma importância para a sobrevivência de uma empresa com grandes ambições.
Pode-se perceber que os Grafos têm grandes utilidades e por isso são tão estudados e implementados nos sistemas das grandes empresas. Alguns exemplos são:
- Redes sociais: Facebook, Instagram, YouTube, etc.
- Caminhos: Google Maps, Maps (Microsoft), etc.
- Sistemas de recomendação: Netflix, Amazon, etc.
Quais são os tipos de Grafos?
Existem muitas variações, iremos abordar a base para que você tenha condições de estudar e se aperfeiçoar futuramente.
Matriz de adjacências
Grafos podem ser representados em formato de matriz:
matriz de adjacências
Fonte: Professor Leonardo Tortoro Pereira
As linhas representam cada vértice e as colunas representam suas arestas. Portanto, se a posição (i,j)=1, então o vértice i possui uma aresta para o vértice j.
Note que na matriz existem apenas números 1, isso ocorre apenas para uma melhor didática. Em uma aplicação real, esses espaços em branco são preenchidos com null (em computação representa um valor nulo) ou por números que informam que a posição está vazia, como por exemplo o -1.
Mas é importante salientar que essa estrutura de grafo exige mais memória para armazenar toda a matriz. Além disso, na computação não é possível aumentar a dimensão de uma matriz, portanto se temos uma matriz A n x n e é necessário adicionar novos vértices, então é preciso criar uma nova matriz B (n+1) x (n+1) e copiar todos os dados de A para B. À vista disso, a forma de matriz de adjacência é recomendada para grafos densos e com poucas adições de novos vértices.
Lista de adjacências
Se sua aplicação possui muitas adições de vértices, então a representação de grafos usando a estrutura de dados lista de adjacências é uma das formas recomendadas para você.
O que são listas?
São uma estrutura de dados, no qual tem o intuito de armazenar dados estruturados no formato de uma lista que podem ou não ser sequenciais. Exemplo: [d0, d1, d2, d3, d4, … , dn] para n ≥ 0.
Lista para n = 3:
representação de um lista
Como a representação de Grafos em Lista de adjacência funciona?
Como o próprio nome já diz, é preciso utilizar listas para representar esse grafo. Mais especificamente, é usado uma lista de listas. Ou seja, temos uma lista em que cada posição representa um vértice e possui uma referência para outra lista, no qual cada posição representa uma aresta. Exemplo:
Listas e grafos. Cedido pelo Professor Leonardo Tortoro Pereira
Note que a posição 1 da lista (primeira coluna), tem referência para outra lista (primeira linha), que possui as arestas apontando para os vértices 2 e 5. Portanto, o vértice 1 possui arestas para o vértice 2 e 5.
Todos os conceitos apresentados servem de base para compreender como é feito os relacionamentos entre usuários do Facebook. Agora é abrir os livros e se aprofundar no conteúdo!
Eai, gostou dessa artigo? Não se esqueça de curtir, compartilhar e visitar nosso blog, sempre temos novidades por lá.
Autor: Adrian Silva