Gráficos na estrutura de dados: tipos, armazenamento e travessia

Uma estrutura de dados é uma maneira eficiente de organizar dados em ciência de dados para que esses dados possam ser acessados ​​facilmente e usados ​​de maneira eficaz. Existem muitos tipos de bancos de dados, mas por que os gráficos desempenham um papel vital no gerenciamento de dados é discutido neste artigo.

Alerta de spoiler: você usa Gráficos na estrutura de dados todos os dias para buscar a melhor rota para o seu escritório, obter sugestões para seu almoço, filme e otimizar sua próxima rota de voo. Soa interessante! Vejamos as propriedades do gráfico e sua aplicação.

Primeiro, vamos ver o que é um Gráfico? É uma representação de dados em uma estrutura não linear que consiste em nós (ou vértices) e arestas (ou caminhos).

Um Grafo na estrutura de dados pode ser denominado como uma estrutura de dados que consiste em dados armazenados entre muitos grupos de arestas (caminhos) e vértices (nós), que são interconectados. A estrutura de dados do gráfico (N, E) é estruturada com uma coleção de nós e arestas. Ambos os nós e vértices precisam ser finitos.

Na representação gráfica acima, Conjunto de nós são N={0,1,2,3,4,5,6}e conjunto de arestas são

G={01,12,23,34,45,05,03}

Agora vamos estudar os tipos de gráficos.

Leia: As 10 principais técnicas de visualização de dados

Tipos de gráficos

1. Gráfico Ponderado

Gráficos cujas arestas ou caminhos possuem valores. Todos os valores vistos associados às arestas são chamados de pesos. O valor das arestas pode representar peso/custo/comprimento.

Os valores ou pesos também podem representar:

• Distância percorrida entre dois pontos- Ex: Para procurar o caminho mais curto para o escritório, a distância entre duas estações de trabalho em uma rede de escritório.
• Velocidade do pacote de dados em uma rede ou largura de banda.

2. Gráfico não ponderado

Onde não há valor ou peso associado à aresta. Por padrão, todos os gráficos não são ponderados, a menos que haja um valor associado.

3. Gráfico não direcionado

Onde um conjunto de objetos está conectado e todas as arestas são bidirecionais. A imagem abaixo mostra o gráfico não direcionado,

É como a associatividade de dois usuários do Facebook depois de se conectarem como amigos. Ambos os usuários podem consultar e compartilhar fotos, comentar entre si.

4. Gráfico direcionado

Também chamado de dígrafo, onde um conjunto de objetos (N, E) são conectados e todas as arestas são direcionadas de um nó para outro. A imagem acima mostra o gráfico direcionado.

Checkout: Projetos de visualização de dados que você pode replicar

Armazenamento do gráfico

Cada método de armazenamento tem seus prós e contras, e o método de armazenamento correto é escolhido com base na complexidade. As duas estruturas de dados mais usadas para armazenar gráficos são:

1. Lista de adjacências

Aqui os nós são armazenados como um índice do array unidimensional seguido pelas arestas sendo armazenadas como uma lista.

2. Matriz de adjacência

Aqui os nós são representados como o índice de uma matriz bidimensional, seguido por arestas representadas como valores diferentes de zero de uma matriz adjacente.

Tanto as linhas quanto as colunas exibem Nós; toda a matriz é preenchida com “0” ou “1”, representando verdadeiro ou falso. Zero representa que não há caminho e 1 representa um caminho.

Percurso do gráfico

Traversal de grafos é um método usado para pesquisar nós em um grafo. A travessia do grafo é usada para decidir a ordem usada para o arranjo dos nós. Ele também procura por arestas sem fazer um loop, o que significa que todos os nós e arestas podem ser pesquisados ​​sem criar um loop.

Existem duas estruturas de travessia de grafos.

1. DFS (Depth First Search): método de pesquisa em profundidade

A pesquisa DFS começa a partir do primeiro nó e se aprofunda cada vez mais, explorando até que o nó de destino seja encontrado. Se a chave de destino não for encontrada, o caminho de pesquisa será alterado para o caminho que foi interrompido durante a pesquisa inicial e o mesmo procedimento será repetido para essa ramificação.

A árvore geradora é produzida a partir do resultado desta busca. Este método de árvore é sem os loops. O número total de nós na estrutura de dados da pilha é usado para implementar a travessia DFS.

Etapas seguidas para implementar a pesquisa DFS:

Etapa 1 – O tamanho da pilha precisa ser definido dependendo do número total de nós.

Passo 2 – Selecione o nó inicial para transversal; ele precisa ser empurrado para a pilha visitando esse nó.

Passo 3 – Agora, visite o nó adjacente que não foi visitado antes e empurre-o para a pilha.

Passo 4 – Repita o Passo 3 até que não haja nenhum nó adjacente que não seja visitado.

Passo 5 – Use backtracking e um nó quando não houver outros nós a serem visitados.

Passo 6 – Esvazie a pilha repetindo os passos 3,4 e 5.

Passo 7 – Quando a pilha está vazia, uma árvore geradora final é formada eliminando as arestas não utilizadas.

As aplicações do DFS são:

• Resolvendo quebra-cabeças com apenas uma solução.
• Para testar se um grafo é bipartido.
• Classificação topológica para agendamento do trabalho e muitos outros.

2. BFS (Breadth-First Search): A pesquisa é implementada usando um método de enfileiramento

A pesquisa em largura navega em um gráfico em um movimento amplo e utiliza com base na fila para pular de um nó para outro, depois de encontrar um final no caminho.

Etapas seguidas para implementar a pesquisa BFS,

Passo 1 – Com base no número de nós, a Fila é definida.

Passo 2 – Comece a partir de qualquer nó da travessia. Visite esse nó e adicione-o à Fila.

Etapa 3 – Agora verifique o nó adjacente não visitado, que está na frente da Fila, e adicione-o à Fila, não ao início.

Passo 4 – Agora comece a deletar o nó que não possui arestas que precisam ser visitadas e não está na Fila.

Passo 5 – Esvazie a fila repetindo os passos 4 e 5.

Passo 6 – Remova as arestas não utilizadas e forme a spanning tree somente depois que a Queue estiver vazia.

As aplicações do BFS são:

• Redes ponto a ponto - Como no Bittorrent, é usado para encontrar todos os nós adjacentes.
• Crawlers no Search Engine.
• Sites de redes sociais e muito mais.

Aplicações do mundo real do gráfico na estrutura de dados

Os gráficos são usados ​​em muitas aplicações do dia-a-dia, como representação de rede (estradas, mapeamento de fibra óptica, projeto de placa de circuito, etc.). Ex: Na rede de dados do Facebook, os nós representam o usuário, sua foto ou comentário, e as bordas representam fotos, comentários sobre a foto.

O Graph na estrutura de dados tem amplas aplicações. Alguns dos notáveis ​​são:

• APIs do Social Graph – É a principal maneira pela qual os dados são comunicados dentro e fora da plataforma de mídia social do Facebook. É uma API baseada em HTTP, que é usada para consultar dados programaticamente, fazer upload de fotos e vídeos, criar novas histórias e muitas outras tarefas. Ele é composto de nós, arestas e campos; para consultar, os nós de objeto específicos são usados. As arestas de um grupo de objetos sujeitos a um único objeto e os campos são usados ​​para buscar dados sobre cada objeto entre o grupo.
• API GraphQL do Yelp – É um mecanismo de recomendação usado para buscar os dados específicos da plataforma Yelp. Aqui, as ordens são usadas para encontrar as arestas, após as quais o nó específico é consultado para buscar o resultado exato. Isso acelera o processo de recuperação.

Na plataforma Yelp, os nós representam o negócio, contendo id, name, is_closed e muitas outras propriedades gráficas.

• Algoritmos de Otimização de Caminho - São empregados para encontrar a melhor conexão que se encaixa nos critérios de velocidade, segurança, combustível, etc. O BFS é usado neste algoritmo. O melhor exemplo é a Plataforma Google Maps (APIs Maps, Routes).
• Redes de voo - Nas redes de voo, isso é usado para encontrar o caminho otimizado que se ajusta à estrutura de dados do gráfico . Isso também auxilia no modelo e otimiza os procedimentos aeroportuários de forma eficiente.

Leia também: Benefícios da visualização de dados

Conclusão

Neste artigo, discutimos primeiro a definição de Graph e Graph na estrutura de dados e, em seguida, aprendemos sobre os tipos de gráficos com suas propriedades. Mais tarde, aprendemos sobre métodos comumente usados ​​para armazenamento de gráficos seguidos por importantes métodos de pesquisa de tópicos usados ​​em Graphs, Graph Traversal. Finalmente, discutimos as aplicações do mundo real da estrutura de dados de grafos.

Este artigo forneceu informações sobre gráficos na estrutura de dados ; o conhecimento disso é vital para a compreensão fundamental em bancos de dados Graph, implementação de algoritmos de pesquisa, programação e muito mais. Deve ser aprendido com o especialista da indústria.

Por que escolher um curso com upGrad ?

Recomendamos que você escolha o Executive PG Program in Data Science oferecido pelo IIIT Bangalore hospedado no upGrad porque aqui você pode tirar suas dúvidas 1-1 com os instrutores do curso. Ele não se concentra apenas no aprendizado teórico, mas dá importância ao conhecimento prático, essencial para preparar os alunos para enfrentar projetos do mundo real e fornecer o 1º certificado NASSCOM da Índia, que ajuda você a obter empregos bem remunerados em Ciência de Dados.

Trabalhos citados

Departamento de Matemática/CS – Home , www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/data-stru.html.

“Percepção Matemática”. Definição de gráfico direcionado – Math Insight , mathinsight.org/definition/directed_graph.

Singh, Amritpal. “Estrutura de dados do gráfico”. Médio , Médio, 29 de março de 2020, medium.com/@singhamritpal49/graph-data-structure-49427c81b3b3.

Só. “As aplicações da vida real de estruturas de dados de gráfico que você deve conhecer.” Graph Data e GraphQL API Development-Leap Graph , leapgraph.com/graph-data-structures-applications.