<Direto ao Ponto 53> Estruturas de Dados - Grafos
- #Informática Básica
Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )
Olá, dev!
Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Ele vai tratar dos grafos, estrutura de dados que não é tão conhecida como as listas, filas e pilhas, mas se tornou conhecida quando passou a modelar as redes sociais.
Sumário
1. Introdução
2. Os grafos
3. Formas de implementação de grafos
4. Exemplos de aplicações implementadas com grafos
5. Considerações finais
6. Referências
1 – Introdução
Eu criei a série de artigos DIRETO AO PONTO com o objetivo de apresentar, de forma simples e direta, conhecimentos básicos da programação e de computação, principalmente, para os iniciantes.
Aqui, são tratados de temas como lógica de programação, linguagens, hardware dos computadores, história da computação e assuntos relacionados à plataforma da DIO, como a escrita de artigos e os desafios de código.
Neste artigo, eu vou falar sobre os grafos e as aplicações que usam grafos na implementação. Alguns exemplos de aplicações com eles servem para modelar redes sociais e modelos geométricos da Computação Gráfica.
2 – Os Grafos
Da mesma forma que as pilhas, os grafos também são um Tipo Abstrato de Dado (TAD), um modelo matemático que especifica um conjunto de dados e as operações que podem ser realizadas sobre eles, sem tratar da implementação destas operações.
Segundo [1], os grafos são uma teoria bem conhecida da matemática e são muito adequados para modelar situações em que pontos podem se conectar com vários pontos adjacentes, como redes de computadores, sociais e outros tipos.
Matematicamente, um Grafo é constituído por um conjunto de vértices, um conjunto de arestas e uma função de incidência.
· Os vértices são elementos interrelacionados pertencentes a um conjunto discreto (enumerável);
· As arestas são elementos de um conjunto discreto que descrevem, de alguma forma, as relações entre os vértices do grafo;
· A função de incidência é uma função que mapeia, para cada aresta do grafo, um par de vértices envolvidos no relacionamento.
Uma representação de um grafo é baseada em nós e vértices, que os ligam uns aos outros. Um nó pode se conectar a um nó, a vários nós ou a nenhum, inclusive a ele mesmo (laço).
Um vértice pode ser direcionado (de um nó a outro), direcionado duplamente (ida e volta de um nó a outro), ou não direcionado (modelando apenas uma conexão entre nós). Além disso, um vértice pode ser ponderado, tendo um valor (peso) associado a ele.
A figura abaixo mostra os diversos tipos de conexão entre os nós de um grafo, não direcionado, direcionado e ponderado (com pesos):
Dependendo da aplicação ou do modelo a ser representado, um grafo pode ser muito simples, complexo e até extremamente complexo. Veja estes tipos de gráficos que modelam pesquisas acadêmicas ou sistemas reais:
Os grafos são utilizados em diversas áreas para modelar relacionamentos e interconexões entre entidades, permitindo análises complexas e otimizadas. A flexibilidade e a ampla aplicabilidade dos grafos fazem deles uma das estruturas de dados mais importantes e poderosas em ciência da computação e em outras disciplinas.
Da mesma forma que as árvores, um grafo pode ter subgrafos, que são subpartes do grafo original:
De acordo com [2], algumas aplicações comuns principais são listadas a seguir:
Roteamento de Dados – (os nós de uma rede de computadores são os roteadores ou computadores, as arestas são as conexões entre os nós). Uma aplicação comum é a determinação das rotas mais eficientes para o tráfego de dados;
Modelagem de Redes Sociais – (nós: usuários, arestas: conexões entre eles). Uma aplicação possível é a identificação dos usuários mais influentes, das comunidades ou dos grupos em que eles interagem;
Sistemas de Recomendação - encontrar padrões e relações entre produtos, filmes, etc, para gerar recomendações personalizadas;
Mapeamento e Navegação – (nós: cruzamentos ou pontos de interesse, arestas: estradas ou rotas). Elaboração de mapas ou indicação de rotas entre 2 pontos;
Inteligência Artificial e ”Machine Learning” – (nós: neurônios, arestas: conexões entre eles). Busca e otimização na análise de redes neurais artificiais;
Processamento de Linguagem Natural (PNL) - modela relações entre palavras em uma frase ou entre palavras e conceitos em redes de conhecimento;
Engenharia de Software e Banco de Dados – modela dependências entre módulos de software;
Jogos e Simulações – (nós: locais ou estados do jogo, arestas: movimentos ou transições). Realiza o mapeamento de cenários do jogo, tomada de decisões e busca por caminhos para os personagens controlados pela IA;
Computação Gráfica – (nós: vértices dos objetos, arestas: arestas e superfícies dos modelos). Modela objetos de uma cena 2D e 3D, permite a realização de operações de posicionamento, translação, rotação e escala dos objetos da cena;
Economia e Finanças – Realizar análise de mercado, modelando as interdependências entre diferentes mercados e ativos financeiros.
Detecção de Fraudes - detecção de padrões incomuns em transações financeiras;
Pesquisa e Otimização de Redes – Projeto de redes de transporte, sistemas de energia e telecomunicações, entre outras.
Operações realizadas em grafos
Busca
Para procurar elementos específicos em grafos, existem duas técnicas básicas:
Busca em profundidade - busca elementos específicos, fazendo uso de funções recursivas e funciona muito bem com grafos do tipo árvore.
Busca em largura - após a verificação de um elemento do grafo, todos os elementos adjacentes são obtidos e verificados. Após o primeiro elemento do grafo ser verificado, todos os elementos adjacentes são obtidos e inseridos em uma fila.
Formas de representação de grafos
Pode-se dizer que um grafo é uma generalização de outras estruturas de dados, como árvores e listas encadeadas. Assim, eles podem ser implementados usando arranjos, registros ou classes ponteiros.
No entanto, de acordo com [3], existem outras formas de se programar os grafos. Duas formas comuns são:
- Lista de Adjacência;
- Matriz de Adjacência.
Grafos podem ser implementados de várias maneiras, dependendo das necessidades da aplicação e do espaço de memória disponível. As formas mais comuns de implementação são:
· Lista de Adjacência - Cada vértice do grafo tem uma lista ligada (ou uma estrutura de lista) que contém todos os vértices adjacentes a ele (ou seja, os vértices conectados por arestas).
· Matriz de Adjacência - É uma matriz bidimensional onde as linhas e colunas representam os nós (vértices) do grafo. O valor na posição (i, j) indica se existe uma aresta entre o vértice i e o vértice j.
Lista de adjacência - Adjacência significa vizinhança. É uma lista de vizinhos. Essa lista é uma estrutura que contém uma lista de adjacências para cada vértice do grafo. A implementação pode usar um dicionário, pois ele permite que as adjacências sejam indexadas com strings ao invés de números naturais.
Na figura abaixo, o vértice 1 tem como seus vizinhos os vértices 2 e 5. Por sua vez, o vértice 2 tem como vizinhos 1, 5, 3 e 4 e assim por diante.
Em uma implementação usando dicionário, cada chave corresponderia a um vértice e o valor atribuído a cada chave seria uma lista com os vizinhos daquele vértice, ou seja, outros vértices conectados a ele.
Matriz de adjacência - Da mesma forma que a lista de adjacências, aqui também são indicados os vértices vizinhos, mas é usada uma matriz.
Na figura a seguir, vemos que nosso grafo tem 5 vértices: 1, 2, 3, 4 e 5. E que o vértice 1 tem duas arestas que o ligam aos vértices 2 e 5. Modelando a relação entre o vértice 1 com outros vértices desse grafo usando um vetor (array) temos:
Aplicando a mesma lógica para todos os vértices, teremos a matriz a seguir, que pode ser implementada por um array bidimensional:
Até poderiam ter sido usados valores booleanos (true e false) pra representar essa matriz, mas se a aplicação precisar de um peso para os vértices (para determinar o tempo gasto em uma rota de um mapa, por exemplo), uma representação que apenas indicasse se há ligação entre os nós não seria adequada.
Uma das aplicações possíveis para os grafos é o problema do menor caminho. Isso já é feito atualmente em aplicativos como Uber, Google Maps e Waze, por exemplo.
3 – Formas de implementação de grafos
Um grafo pode ser implementado de várias maneiras: usando vetor estático, lista encadeada (com ponteiros), com um tipo lista (list) ou por um tipo específica (Stack). Vamos ver um resumo de cada uma delas.
Na implementação de grafos, os tipos de dados mais usados são escolhidos com base em fatores como a estrutura do grafo (denso ou esparso), a eficiência necessária e a facilidade de manipulação. Aqui estão os tipos de dados mais comumente usados:
I - IMPLEMENTAÇÃO COM LISTA ENCADEADA
Ponteiros são frequentemente usados em linguagens de baixo nível, como C, para implementar listas encadeadas que representam listas de adjacência. Também são usados em estruturas de grafos dinâmicos.
Exemplo de uma estrutura de um nó para uma lista em C
(Lista de Adjacência com Ponteiros):
typedef struct Node {
int vertex;
struct Node* next;
} Node;
II - A IMPLEMENTAÇÃO COM VETOR ESTÁTICO
Matrizes de adjacência são usadas quando precisamos de uma representação simples de grafos e eficiência na verificação da existência de uma aresta entre dois nós.
Exemplo em C/C++:
int graph[4][4] = {
{0, 1, 1, 0},
{1, 0, 0, 1},
{1, 0, 0, 1},
{0, 1, 1, 0}
};
III - A IMPLEMENTAÇÃO USANDO A ESTRUTURA LIST
A implementação mais comum para grafos é a lista de adjacência, que pode ser construída usando listas ligadas ou outras estruturas de lista (como arrays dinâmicos ou listas encadeadas).
Exemplo em Python:
# Grafo representado como uma lista de adjacência
grafo = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
IV - A IMPLEMENTAÇÃO USANDO UM TIPO ESPECÍFICO PARA GRAFOS
Muitas linguagens de programação oferecem tipos específicos ou bibliotecas para a manipulação de grafos. Estes são otimizados e incluem algoritmos eficientes. Por exemplo:
· C++: A biblioteca Boost Graph Library (BGL) oferece uma coleção completa de implementações de grafos;
· Python: A biblioteca NetworkX permite a criação, manipulação e estudo de grafos complexos;
· Java: Estruturas como TreeMap e HashMap podem ser usadas para grafos, ou pode-se usar bibliotecas de terceiros;
· C#: Estruturas como Dicionário, combinadas com listas são frequentemente usadas para grafos.
Cada abordagem tem suas próprias vantagens e limitações, e a escolha correta depende do contexto e das operações que você precisa realizar no grafo.
4. Exemplos de aplicações implementadas com grafos
A seguir, seguem alguns programas básicos que implementam pilhas, em linguagens diferentes:
NA LINGUAGEM PASCAL – USANDO VETOR ESTÁTICO
Implementação de Grafo usando Vetores em Pascal (Matriz de Adjacência)
program GrafoMatrizAdjacencia;
const
MAX_VERTICES = 5;
type
MatrizAdjacencia = array[1..MAX_VERTICES, 1..MAX_VERTICES] of integer;
var
grafo: MatrizAdjacencia;
i, j: integer;
begin
{ Inicializa a matriz de adjacência com 0 }
for i := 1 to MAX_VERTICES do
for j := 1 to MAX_VERTICES do
grafo[i, j] := 0;
{ Adiciona arestas ao grafo }
grafo[1, 2] := 1;
grafo[2, 3] := 1;
grafo[3, 4] := 1;
grafo[4, 5] := 1;
grafo[5, 1] := 1;
{ Exibe a matriz de adjacência }
writeln('Matriz de Adjacência:');
for i := 1 to MAX_VERTICES do
begin
for j := 1 to MAX_VERTICES do
write(grafo[i, j]:3);
writeln;
end;
end.
Saída do programa
Matriz de Adjacência:
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
LINGUAGEM C – USANDO LISTA ENCADEADA COM PONTEIROS
Lista de Adjacência
#include <stdio.h>
#include <stdlib.h>
// Estrutura para um nó na lista de adjacência
typedef struct No {
int vertice;
struct No* prox;
} No;
// Estrutura para o grafo
typedef struct Grafo {
int numVertices;
No** listaAdj; // Array de ponteiros para listas de adjacência
} Grafo;
// Função para criar um nó
No* criarNo(int vertice) {
No* novoNo = malloc(sizeof(No));
novoNo->vertice = vertice;
novoNo->prox = NULL;
return novoNo;
}
// Função para criar um grafo
Grafo* criarGrafo(int vertices) {
Grafo* grafo = malloc(sizeof(Grafo));
grafo->numVertices = vertices;
grafo->listaAdj = malloc(vertices * sizeof(No*));
for (int i = 0; i < vertices; i++)
grafo->listaAdj[i] = NULL;
return grafo;
}
// Função para adicionar uma aresta ao grafo
void adicAresta(Grafo* grafo, int de, int para) {
// Adiciona a aresta do destino (de) para o destino (para)
No* novoNo = criarNo(de);
novoNo->prox = grafo->listaAdj[de];
grafo->listaAdj[de] = novoNo;
// Adiciona a aresta do dest para o src (grafo não direcionado)
novoNo = criarNo(de);
novoNo->prox = grafo->listaAdj[para];
grafo->listaAdj[para] = novoNo;
}
// Função para imprimir o grafo
void mostrarGrafo(Grafo* grafo) {
for (int v = 0; v < grafo->numVertices; v++) {
No* temp = grafo->listaAdj[v];
printf("\n Lista de adjacência do vértice %d\n ", v);
while (temp) {
printf("%d -> ", temp->vertice);
temp = temp->prox;
}
printf("NULL\n");
}
}
int main() {
int vertices = 5;
Grafo* grafo = criarGrafo(vertices);
adicAresta(grafo, 0, 1);
adicAresta(grafo, 0, 4);
adicAresta(grafo, 1, 2);
adicAresta(grafo, 1, 3);
adicAresta(grafo, 1, 4);
adicAresta(grafo, 2, 3);
adicAresta(grafo, 3, 4);
mostrarGrafo(grafo);
return 0;
}
Saída do Programa
Lista de adjacência do vértice 0
4 -> 1 -> NULL
Lista de adjacência do vértice 1
4 -> 3 -> 2 -> 0 -> NULL
Lista de adjacência do vértice 2
3 -> 1 -> NULL
Lista de adjacência do vértice 3
4 -> 2 -> 1 -> NULL
Lista de adjacência do vértice 4
3 -> 1 -> 0 -> NULL
NA LINGUAGEM PYTHON – USANDO A BIBLIOTECA NetworkX
(Lista de Adjacência)
# Exemplo de grafo representado como uma lista de adjacência
grafo = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
Exemplo de Código em Python usando NetworkX
import networkx as nx # cria e manipula os grafos
import matplotlib.pyplot as plt # desenha o grafo visualmente
# Cria um grafo vazio
G = nx.Graph()
# Adiciona nós ao grafo
G.add_node('A')
G.add_nodes_from(['B', 'C', 'D', 'E'])
# Adiciona arestas ao grafo
G.add_edge('A', 'B')
G.add_edges_from([('A', 'C'), ('B', 'D'), ('C', 'D'), ('D', 'E')])
# Exibe informações sobre o grafo
print("Nós do grafo:", G.nodes())
print("Arestas do grafo:", G.edges())
# Desenha o grafo usando Matplotlib
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_color='lightblue', edge_color='gray', node_size=1000, font_size=16)
plt.title("Representação Gráfica do Grafo com NetworkX")
plt.show()
Saída do programa
Nós do grafo: ['A', 'B', 'C', 'D', 'E']
Arestas do grafo: [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('D', 'E')]
5 – Considerações finais
Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Neste artigo eu tratei das pilhas, mais um Tipo Abstrato de Dado (TAD), juntamente com as listas e filas.
Os grafos têm sua base conceitual na matemática e são muito usados para modelar situações em que pontos podem se conectar com vários pontos adjacentes, como as redes (redes de computadores, redes sociais etc.).
Basicamente, um grafo é composto nós e vértices, que ligam os nós uns aos outros. Os vértices podem ser ponderados, com um valor como peso, como nos ramos das redes neurais.
Na programação, os grafos são aplicados na modelagem dos dados em diversas áreas, como no roteamento de dados, sistemas de recomendação, mapeamento e navegação, IA, detecção de fraudes financeiras etc.
Da mesma forma que as árvores, filas e pilhas, os grafos podem ser implementados de várias formas, usando vetores estáticos, listas encadeadas com ponteiros, ou com classes e bibliotecas específicas, como a NetworkX, do Python.
Neste artigo foram apresentados os conceitos básicos dos grafos, seus tipos mais comuns e foram listadas algumas áreas onde eles podem ser utilizados.
Foram escritos códigos para implementação de grafos usando várias formas diferentes, incluindo uma biblioteca específica para manipulá-los.
Este artigo encerra um conjunto de artigos (9) dedicados às estruturas de dados, tema essencial como base para a área de programação, juntamente com a lógica de programação e os algoritmos, também já tratados em artigos anteriores.
Nestes últimos 9 artigos, eu apresentei conceitos, tipos, formas de implementação e exemplos de códigos (todos testados e rodando perfeitamente) das estruturas mais básicas da programação, como vetores, cadeias de caracteres, matrizes, listas, filas, pilhas, árvores e grafos.
Ainda existem outros tipos que não foram tratados em um artigo próprio, mas também são muito usadas e importantes também, resumidas aqui:
· Tabela Hash (”hash table”) – É uma estrutura de dados que armazena pares de chave-valor, usando uma função de hash para calcular o índice de armazenamento.
· Mapa hash (“hash map”) - Conceito genérico para uma estrutura de dados que usa uma tabela hash para mapear chaves a valores.
· Dicionário (dictionary) - Estrutura de dados que armazena pares de chave-valor. Internamente, ele é implementado usando uma tabela hash, onde as chaves são mapeadas para valores. Exemplo em Python:
meu_dicionario = {'chave1': 'valor1', 'chave2': 'valor2'}
· Conjunto (set) - é uma coleção de elementos únicos, e sua implementação também é baseada em uma tabela hash, semelhante aos dicionários. No entanto, os sets não armazenam pares de chave-valor; eles armazenam apenas valores. Exemplo em Python:
meu_conjunto = {1, 2, 3, 4}
No próximo artigo, eu vou contar uma história pessoal: o dia em que eu inventei as listas encadeadas.
:-)
6 – Referências
[1] Filipe C. FERRAZ, Grafos e algoritmos. Disponível em < https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416>. Acesso em 17/10/2024.
[2] Ramon SORAGE, Grafos #2: Diferentes tipos de grafos com exemplos práticos. Disponível em <https://medium.com/@rsorage/grafos-2-diferentes-tipos-de-grafos-com-exemplos-pr%C3%A1ticos-e4646c4f1ce2>. Acesso em 17/10/2024.
[3] Ramon SORAGE, Grafos #1: introdução de forma fácil. Disponível em <https://medium.com/@rsorage/grafos-introdu%C3%A7%C3%A3o-de-forma-f%C3%A1cil-a4959821e101>. Acesso em 17/10/2024.
Para criar os códigos dos exemplos, eu consultei o ChatGPT e fiz algumas correções necessárias para sair do jeito que eu queria. Todos os códigos foram testados e rodaram sem problemas.
Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )