Olá, hoje eu vou contar um pouco para vocês sobre a teoria dos grafos, este é um de uma série de posts que pretendo fazer sobre algoritmos, ensinando o que eu aprendi no meu ponto de vista. No final do post vou listar as minhas referencias, quero ressaltar que este não é um post que tem o intuito de ser um artigo acadêmico e não deve ser tratado como tal, estou escrevendo isso com o intuito de simplificar um conteúdo que é extenso e de certa forma complexo, e quero convidar vocês a procurar as minhas fontes, tenho certeza de que após a essa pequena introdução e procurar as minhas fontes, você vai perceber que algoritmos não são o bicho de 7 cabeças que dizem ser.
O que são algoritmos?
“Um algoritmo é literalmente um processo sistemático para a resolução de um problema.” Jayme Luiz Szwarcfiter
Acho que essa frase resume bem o que é um algoritmo, e aprender algoritmos e estruturas de dados, vão te auxiliar muito na hora de fazer uma entrevista técnica caso queira trabalhar na área. Até mesmo na vida no geral, melhora a tua capacidade de resolução de problemas, te faz pensar de uma forma diferente quando você vê um problema e tenta resolver esse problema.
Vamos começar com o que são grafos! Grafos são exatamente estruturas matemáticas que permitem codificar relacionamentos entre pares de objetos (Resumindo, são conjunto de vértices conectados por arestas). Dentro da teoria dos grafos temos grafos direcionados e grafos não direcionados, a diferença de um para o outro são as rotas das arestas, nos grafos não direcionados tanto faz a direção das arestas, no exemplo abaixo podemos nos locomover tanto do dois para o três quanto do três para o dois, o que não se aplicaria se o grafo fosse direcionado. E para um grafo ficar bem definido temos que ter dois conjuntos: O conjunto V dos vértices e o conjunto A das arestas. Para ficar mais fácil de entender, vamos ilustrar com alguns exemplos.
Aqui na imagem, podemos ver claramente o conjunto A das arestas e o conjunto V que na imagem é representado com números. Mas onde usamos isto? Nós usamos grafos para quase tudo nessa vida, literalmente tudo na natureza da para representar com grafos, na tecnologia então, nem se fala… Um bom exemplo é o algoritmo de recomendação do Twitter deixei essa imagem abaixo que foi tirada do video do Fabio Akita sobre o algoritmo do Twitter.
Nesse grafo do Twitter os vértices são as pessoas e as arestas são os relacionamentos (Quem seguimos, damos like, reetwitamos até mesmo quem bloqueamos). Provavelmente vocês devem estar pensando que isso é coisa de outro mundo, vou deixar outro exemplo para vocês… As rotas dos transportes públicos, cada estação é um vértice, e as arestas estão onde são as linhas.
O Dna Humano, pode ser representado por um grafo, suas bases hidrogenadas são seus vértices (adenina (A), guanina (G), citosina © e timina (T).)
Até mesmo as sinapses cerebrais do ser humano pode ser representado por um grafo. As sinapses cerebrais são junções entre a terminação de um neurônio e a membrana de outro neurônio. São elas que fazem a conexão entre células vizinhas, dando continuidade à propagação do impulso nervoso por toda a rede neuronal.
Agora eu vou deixar um exemplo de um grafo não direcionado que eu fiz em Python (escolhi Python por ser uma linguagem simples de entender e de ilustrar este exemplo):
import networkx as nx
"""Aqui vou criar uma função que cria um grafo não direcionado, vou adicionar os vértices (ou nós) e vou adicionar as arestas (conexões entre os vertices)"""
def grafoN():
G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4, 5])
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 1)])
return G
G = grafoN()
print("Número de nós:", G.number_of_nodes())
print("Número de arestas:", G.number_of_edges())
print("Nós:", list(G.nodes()))
print("Arestas:", list(G.edges()))
O output esperado é:
Número de nós: 5
Número de arestas: 6
Nós: [1, 2, 3, 4, 5]
Arestas: [(1, 2), (1, 3), (1, 5), (2, 4), (3, 4), (4, 5)]
No exemplo utilizado, definimos um grafo não direcionado com cinco nós e seis arestas, utilizamos a biblioteca NetworkX para acessar informações como o número de nós e arestas, bem como listar os nós e arestas presentes no grafo. Para ilustrar de forma mais clara desenhei este exemplo de como ficaria esse grafo!
Nesse grafo em especifico os nós (ou vértices) são ilustrados com números para facilitar a sua compreensão. Esses são grafos não direcionados, agora vou falar sobre os grafos direcionados
Os grafos direcionados são utilizados em diversas aplicações práticas, como modelagem de fluxos de informações, redes de transporte, sistemas de navegação, entre outros. A capacidade de representar e analisar relações direcionadas entre elementos torna os grafos direcionados uma ferramenta poderosa para entender a dinâmica de sistemas complexos e orientados por fluxos. Nos grafos direcionados cada aresta possui uma seta indicando a direção do fluxo entre os vértices. Isso reflete a natureza direcional das relações representadas no grafo. Os vértices são dispostos no plano de acordo com as coordenadas e configurações definidas na representação gráfica. A estilização, incluindo cores, tamanhos e fontes, contribui para uma visualização clara da estrutura de rede direcionada. Aqui vou deixar mais um exemplo de um grafo só que dessa vez direcionado:
import networkx as nx
def grafoD():
G = nx.DiGraph()
G.add_nodes_from([1, 2, 3, 4, 5])
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 1)])
return G
G = grafoD()
print("Número de nós:", G.number_of_nodes())
print("Número de arestas:", G.number_of_edges())
print("Nós:", list(G.nodes()))
print("Arestas:", list(G.edges()))
Output esperado:
Número de nós: 5
Número de arestas: 6
Nós: [1, 2, 3, 4, 5]
Arestas: [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 1)]
Vou deixar um exemplo ilustrativo de como é um grafo direcionado abaixo:
Perceba que no grafo direcionado no exemplo acima nós podemos ir do quatro pro cinco, mas não podemos ir diretamente do cinco para o quatro, isso ocorre porquê nós não temos arestas indo do cinco pro quatro, só temos arestas indo do quatro pro cinco. Rotas estabelecidas (1 -> 2), (1 -> 3), (2 -> 4), (3 -> 4), (4 -> 5), (5 -> 1).
Referências:
Fabio Akita falando sobre o algoritmo do twitter: https://youtu.be/uIflMYQnp8A?si=3IXMSGUUOfrcTPwS
Link do pdf do livro entendendo algoritmos:
https://github.com/KAYOKG/BibliotecaDev/blob/main/LivrosDev/Entendendo%20Algoritmos%20-%20Um%20Guia%20Ilustrado%20Para%20Programadores%20e%20Outros%20Curiosos%20-%20Autor%20(Aditya%20Y.%20Bhargava).pdf
Playlist de uma introdução à teoria dos grafos:
https://www.youtube.com/playlist?list=PLrVGp617x0hAm90-7zQzbRsSOnN2Vbr-I
Link do meu github:
https://github.com/BrunoCiccarino
Top comments (0)