A Representação da Estrutura de Dados

Prévia do material em texto

Material Complementar:
A Representação da Estrutura de Dados: 
os Grafos Conectados 
2
A Representação da Estrutura de Dados: os Grafos Conectados 
Este texto aborda as questões relacionadas com a estrutura de grafos no contexto 
do Big Data. 
O que São os Grafos?
Os grafos são estruturas não lineares e ubíquas com ampla utilização em diversos 
domínios de aplicações, tanto em organizações públicas como privadas. Essas 
estruturas permitem representar relações entre objetos e são amplamente utilizadas 
em ciência da computação, engenharia, física entre outras áreas (Magalhães, 2015). 
Grafo é um tema relativamente comum na computação, mas ainda um pouco distante 
de alguns gestores públicos. Com o Big Data, o processamento e armazenamento 
dos grafos tem exigido o uso de novas técnicas e ferramentas (Magalhães, 2015). 
Os grafos são compostos por vértices (conhecidos por nós) e arestas. Os vértices 
representam os objetos que estão sendo relacionados e as arestas representam 
as relações entre esses objetos. As arestas podem ter uma direção (conhecidas por 
arestas direcionadas) ou não (conhecidas por arestas não-direcionadas). 
Existem várias maneiras de representar grafos, incluindo matrizes de adjacência, 
listas de adjacência e outras estruturas de dados. A escolha da representação 
depende do tipo de problema que está sendo resolvido e do tamanho dos dados. 
Os grafos são usados em muitos problemas práticos, incluindo redes sociais, rotas de 
transporte, planejamento de roteamento de fábricas, análise de dados biomédicos, 
análise de tráfego de rede e muito mais. 
Os grafos têm várias vantagens em relação a outras estruturas de dados como 
matrizes ou listas. As principais vantagens dos grafos incluem: 
• Modelagem de relações complexas: os grafos são adequados para
representar relações complexas entre objetos que não podem ser facilmente 
modeladas por outras estruturas de dados. Por exemplo, as relações entre
as pessoas em uma rede social são melhor representadas por um grafo do
que por uma matriz ou lista.
• Eficiência em operações de busca e percurso: as operações de busca
e percurso em grafos são muito eficientes, já que a estrutura de dados é
projetada para facilitar esse tipo de operação. Sendo assim, tem grande
utilidade na análise de grande quantidade de dados.
3
• Flexibilidade: os grafos são flexíveis e podem ser usados para resolver
uma ampla variedade de problemas.
• Representação visual: os grafos são frequentemente representados
visualmente, o que facilita a compreensão das relações entre os objetos.
Essa representação visual pode ser particularmente útil para análise de
dados e tomada de decisões.
• Adaptação para crescimento de dados: os grafos podem ser facilmente
adaptados para lidar com grandes conjuntos de dados.
Os Tipos de Grafos 
A utilização dos grafos tem aumentado de forma exponencial no ambiente do Big 
Data, tendo cada um dos tipos características distintas e adequadas para resolver 
diferentes problemas. Os tipos mais comuns de grafos compreendem: 
Grafo não-direcionado: é um tipo de grafo em 
que as arestas não têm direção. Sendo assim, 
a relação entre dois vértices é bidirecional;
Grafo direcionado: é um tipo de grafo em que 
as arestas têm uma direção. Sendo assim, a 
relação entre dois vértices é unidirecional. 
Grafo não-direcionado. 
Fonte: autor.
Grafo direcionado. 
Fonte: autor.
4
Grafo ponderado: é um tipo de grafo em que 
as arestas têm um peso ou valor associado a 
elas. É útil quando a relação entre dois vértices 
tem uma importância ou significado diferente. 
Grafo completo: é um tipo de grafo em que 
cada par de vértices está conectado por uma 
aresta. Ou seja, todos os vértices do grafo 
estão interconectados. 
Grafo bipartido: é um tipo de grafo em que os 
vértices podem ser divididos em dois grupos, 
de forma que cada aresta liga um vértice de 
um grupo a um vértice do outro grupo. 
Grafo cíclico: é um tipo de grafo em que há 
pelo menos um ciclo, ou seja, uma sequência 
de vértices interconectados que se conectam 
novamente no vértice inicial. 
Grafo ponderado. 
Fonte: autor.
Grafo completo. 
Fonte: autor.
Grafo bipartido. 
Fonte: autor.
Grafo cíclico. 
Fonte: autor.
5
Grafo acíclico: é um tipo de grafo em que não 
há ciclos, ou seja, não há uma sequência de 
vértices interconectados que se conectam 
novamente no vértice inicial. 
Grafo conexo: é um tipo de grafo em que todos 
os vértices estão conectados por pelo menos 
uma aresta. Isso significa que é possível chegar 
a qualquer vértice a partir de qualquer outro 
vértice através de uma série de arestas. Caso 
contrário, o grafo é chamado de desconexo 
Grafo como árvore: é um tipo de grafo que 
possibilita ir de um vértice para outro, sem 
voltar ao mesmo vértice. 
Grafo planar: é um tipo de grafo que pode ser 
desenhado em um plano de tal forma que suas 
arestas não se cruzem. Sendo assim, esses grafos 
podem ser representados em duas dimensões.
Grafo acíclico. 
Fonte: autor.
Grafo conexo e grafo desconexo. 
Fonte: autor.
Grafo como árvore. 
Fonte: autor.
Grafo cíclico. 
Fonte: autor.
Grafo planar. 
Fonte: autor.
6
A escolha do tipo de grafo mais adequado para um problema específico depende 
das características do problema e dos dados envolvidos. 
O Conceito de Complexidade nos Grafos 
A complexidade em grafos está relacionada à dificuldade de resolver problemas 
específicos em um grafo. Alguns problemas em grafos podem ser resolvidos de 
maneira eficiente, enquanto outros podem ser muito mais difíceis de resolver. 
A teoria da complexidade dos grafos é um campo ativo de pesquisa em ciência da 
computação e matemática, importante para o desenvolvimento de algoritmos 
eficientes para problemas relacionados aos grafos. 
A complexidade dos grafos apresenta desafios relacionados à capacidade de 
processamento e armazenamento de grandes grafos. Com isso, os desafios mais 
comuns relacionados à complexidade dos grafos compreendem: 
• Problema do caminho mais curto: encontrar o caminho mais curto entre
dois nós de um grafo ponderado. Este problema pode ser resolvido usando
o algoritmo de Dijkstra (veja aqui), que é eficiente para grafos com pesos
positivos, mas pode ser ineficiente em grafos com pesos negativos.
• Problema do caixeiro-viajante: encontrar o caminho mais curto que visite
cada nó exatamente uma vez e retorne ao nó inicial de um grafo ponderado.
Este problema é conhecido como NP-completo, o que significa que não existe
um algoritmo eficiente conhecido para resolvê-lo em todos os casos.
• Problema do fluxo máximo: encontrar o fluxo máximo entre um nó de
origem e um nó de destino em um grafo ponderado. Este problema pode ser
resolvido usando o algoritmo de Ford-Fulkerson (veja aqui), que é eficiente
em grafos pequenos mas pode ser ineficiente em grafos grandes.
• Problema da coloração de vértices: encontrar uma coloração para os
vértices de modo que vértices adjacentes de um grafo tenham cores diferentes. 
Este problema também é conhecido como NP-completo, não existindo um
algoritmo eficiente conhecido para resolvê-lo em todos os casos.
• Problema da árvore geradora mínima: encontrar a árvore geradora mínima
para um grafo ponderado, que é uma subestrutura do grafo que conecta todos
os nós com o menor peso possível. Esse problema pode ser resolvido usando o
algoritmo de Kruskal (veja aqui) ou o algoritmo de Prim (veja aqui).
https://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html#:~:text=O%20Algoritmo%20de%20Dijkstra%20(E.W.,um%20bom%20n%C3%ADvel%20de%20performance
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/flow-FF.html#:~:text=O%20algoritmo%20de%20Ford%2DFulkerson%2C%20tamb%C3%A9m%20conhecido%20como%20algoritmo%20dos,come%C3%A7a%20com%20o%20fluxo%20nulo
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/kruskal.html
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/prim.html
7
Diversas técnicas e algoritmos em teoria dos grafos, como os algoritmos de 
busca exaustiva; os algoritmosde programação dinâmica; os algoritmos de 
heurística; e as técnicas de otimização, apresentam abordagens diferentes 
para resolver problemas computacionais. Cada abordagem tem seus pontos 
fortes e fracos, por isso é importante escolher a abordagem adequada para 
um determinado problema. 
• Algoritmos de busca exaustiva: os algoritmos de busca exaustiva
tentam examinar todas as soluções possíveis para um problema. Esses
algoritmos geralmente são úteis quando o tamanho do espaço de
soluções é pequeno o suficiente para que todas as soluções possam ser
examinadas em tempo razoável.
• Algoritmos de programação dinâmica: os algoritmos de programação
dinâmica dividem um problema em subproblemas menores e, em seguida,
resolvem os subproblemas de maneira recursiva, combinando as soluções
para resolver o problema original. Esses algoritmos são especialmente úteis
quando há sobreposição de subproblemas.
• Algoritmos de heurística: os algoritmos de heurística usam abordagens
aproximadas para encontrar soluções para um problema. Esses algoritmos
geralmente são úteis quando o tamanho do espaço de soluções é grande
demais para que todas as soluções possam ser examinadas em tempo
razoável.
• Técnicas de otimização: as técnicas de otimização usam algoritmos
matemáticos para encontrar a melhor solução para um problema. Essas
técnicas geralmente são úteis quando o problema pode ser modelado como
uma função matemática que pode ser otimizada.
A Conexão nos Grafos 
A conexão é um conceito-chave em grafos, já que faz referência à capacidade de se 
mover de um vértice para outro por meio de um caminho formado por uma ou mais 
arestas. Essa capacidade de conexão é fundamental para análise e solução de diversos 
problemas práticos, como por exemplo: 
• Roteamento em redes de computadores: a conexão dos grafos é
fundamental para o roteamento de pacotes em redes de computadores.
Os roteadores utilizam informações de conexão entre os dispositivos para
determinar a melhor rota para encaminhar os pacotes de dados.
8
• Planejamento de rotas em logística: a conexão dos grafos é funcional
na determinação de rotas eficientes para o transporte de mercadorias. Por
exemplo, a conexão de cidades em um mapa permite a identificação da rota
mais curta para a entrega de produtos.
• Design de circuitos eletrônicos: a conexão dos grafos é empregada no design
de circuitos eletrônicos. Os componentes do circuito são representados como
vértices e as conexões entre eles como arestas, possibilitando a identificação
de problemas de conexão e a otimização da disposição dos componentes.
• Análise de redes sociais: a conexão dos grafos é aplicada na análise de
redes sociais, tornando possível a identificação de grupos de usuários com
interesses semelhantes, influenciadores e padrões de comportamento dos
usuários.
• Planejamento de rotas em transporte público: a conexão dos grafos é
essencial na determinação de rotas eficientes para o transporte público. As
conexões entre as estações de transporte público são representadas como
arestas e os veículos como vértices, ajudando no processo para determinar a
rota mais rápida para a locomoção de passageiros.
As vantagens da conexão em grafos incluem: 
• Facilidade de navegação: a conexão dos grafos permite a movimentação
entre vértices, o que é importante para a navegação em redes e sistemas
complexos.
• Eficiência em análise: a conexão dos grafos permite a análise de propriedades
globais do sistema, o que pode ser prático para a identificação de gargalos ou
pontos críticos.
• Resolução do problema do caminho mais curto: a conexão dos grafos é
fundamental para a solução do problema do caminho mais curto, gerando,
por exemplo, economia de tempo; recursos; otimização de processos; e rotas
mais eficientes para o planejamento urbano ou no contexto da logística.
Representação visual: a conexão dos grafos permite que as informações 
sejam representadas visualmente, fato que pode ajudar a identificar padrões 
e relações complexas. 
9
Magalhães, Regis Pires. Processamento de Grafos em Big Data. [S. l.: s. n.], 2015.
Referências