Introdução ao gráfico na estrutura de dados

Os gráficos são estruturas de dados não lineares que compreendem um conjunto finito de nós e arestas. Os nós são os elementos e as arestas são pares de conexões ordenados entre os nós.

Observe a palavra não linear. Uma estrutura de dados não linear é aquela em que os elementos não estão organizados em ordem sequencial. Por exemplo, uma matriz é uma estrutura de dados linear porque os elementos são organizados um após o outro. Você pode percorrer todos os elementos de uma matriz em uma única execução. Esse não é o caso de estruturas de dados não lineares. Os elementos de uma estrutura de dados não linear são organizados em vários níveis, geralmente seguindo um padrão hierárquico. Os gráficos não são lineares.

A próxima palavra para prestar atenção é finita. Definimos o gráfico para ter um número finito e contável de nós. Este é um termo bastante inaceitável. Essencialmente, um gráfico pode ter um número infinito de nós e ainda ser finito. Por exemplo, uma árvore genealógica que remonta a Adão e Eva. Este é um gráfico relativamente infinito, mas ainda é contável e, portanto, é considerado finito.

Exemplo do mundo real

O melhor exemplo de gráficos no mundo real é o Facebook. Cada pessoa no Facebook é um nó e é conectada através de bordas. A é amigo de B. B é amigo de C e assim por diante.

Terminologias

Aqui estão as terminologias do gráfico na estrutura de dados mencionadas abaixo

1. Representação gráfica: Geralmente, um gráfico é representado como um par de conjuntos (V, E). V é o conjunto de vértices ou nós. E é o conjunto de arestas. No exemplo acima,
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)

2. Nó ou vértice: os elementos de um gráfico são conectados através de arestas.

3. Arestas: um caminho ou uma linha entre dois vértices em um gráfico.

4. Nós adjacentes: Dois nós são chamados adjacentes se estiverem conectados por uma borda. No exemplo acima, o nó A é adjacente aos nós B, C e D, mas não ao nó E.

5. Caminho: Caminho é uma sequência de arestas entre dois nós. É essencialmente um percurso que começa em um nó e termina em outro. No exemplo acima, há vários caminhos do nó A para o nó E.

Caminho (A, E) = (AB, BE)
OU
Caminho (A, E) = (AC, CD, DE)
OU
Caminho (A, E) = (AD, DE)

6. Gráfico não direcionado : Um gráfico não direcionado é aquele em que as arestas não especificam uma direção específica. As arestas são bidirecionais.

Exemplo

Assim, neste exemplo, a aresta AC pode ser atravessada de A a C e C a A. Semelhante a todas as arestas. Um caminho do nó B para o nó C seria (BA, AC) ou (BD, DC).

7. Gráfico direcionado: Um gráfico direcionado é aquele em que as bordas podem ser atravessadas apenas em uma direção especificada.

Exemplo

Assim, no mesmo exemplo, agora as arestas são direcionais. Você só pode atravessar a borda ao longo de sua direção. Não há caminho do nó B para o nó C agora.

8. Gráfico ponderado : um gráfico ponderado é aquele em que as arestas estão associadas a um peso. Geralmente, esse é o custo para atravessar a borda.

Exemplo

Assim, no mesmo exemplo, agora as arestas têm um certo peso associado a elas. Existem dois caminhos possíveis entre o nó A e o nó E.
Caminho1 = (AB, BD, DE), Peso1 = 3 + 2 + 5 = 10
Caminho2 = (CA, CD, DE), Peso2 = 1 + 3 + 5 = 9
Claramente, seria preferível o Path2 se o objetivo é alcançar o nó E do nó A com custo mínimo.

Operações básicas no gráfico

Aqui estão as operações básicas do gráfico mencionadas abaixo

1. Adicionar / Remover Vértice

Esta é a operação mais simples do gráfico. Você simplesmente adiciona um vértice a um gráfico. Ele não precisa ser conectado a nenhum outro vértice através de uma aresta. Ao remover um vértice, você deve remover todas as arestas originadas e terminadas no vértice excluído.

2. Adicionar / remover borda

Esta operação adiciona ou remove uma aresta entre dois vértices. Quando todas as arestas originadas e terminadas em um vértice são excluídas, o vértice se torna um vértice isolado.

3. Pesquisa de Largura Primeira (BFS)

Esta é uma operação transversal no gráfico. O BFS percorre horizontalmente o gráfico. Isso significa que ele percorre todos os nós em um único nível antes de prosseguir para o próximo nível.
O algoritmo BFS inicia na parte superior do primeiro nó no gráfico e, em seguida, percorre todos os nós adjacentes a ele. Depois que todos os nós adjacentes são percorridos, o algoritmo repete o mesmo procedimento para nós filho.

Exemplo

Atravessar o gráfico acima no modo BFS resultaria de A -> B -> C -> D -> E -> F -> G. O algoritmo inicia no nó A e percorre todos os seus nós adjacentes B, C e D. todos os quatro nós como visitados. Uma vez percorridos todos os nós adjacentes de A, o algoritmo se move para o primeiro nó adjacente de A e repete o mesmo procedimento. Nesse caso, o nó é B e os nós adjacentes a B são E e F. Em seguida, os nós adjacentes a C são atravessados. Depois que todos os nós são visitados, a operação termina.

4. Pesquisa profunda (DFS)

A profundidade de pesquisa inicial ou DFS percorre o gráfico verticalmente. Ele começa com o nó raiz ou o primeiro nó do gráfico e percorre todos os nós filhos antes de passar para os nós adjacentes.

Exemplo

Atravessar o gráfico acima no modo BFS resultaria de A -> B -> E -> F -> C -> G -> D. O algoritmo inicia no nó A e percorre todos os seus nós filhos. Assim que encontra B, parece que ele tem outros nós filhos. Portanto, os nós filhos de B são percorridos antes de prosseguir para o próximo nó filho de A.

Implementações reais de gráficos

  • Projeto de circuitos elétricos para transmissão de energia.
  • Projeto de rede de computadores interconectados.
  • Estudo da estrutura molecular, química e celular de qualquer substância, por exemplo, DNA humano.
  • Design de rotas de transporte entre cidades e locais dentro de uma cidade.

Conclusão - Gráfico na estrutura de dados

Os gráficos são um conceito muito útil em estruturas de dados. Possui implementações práticas em quase todos os campos. É muito importante entender o básico da teoria dos grafos, desenvolver um entendimento dos algoritmos da estrutura dos grafos.
Este artigo foi apenas uma introdução aos gráficos. É apenas um trampolim. Recomenda-se aprofundar ainda mais no tópico da teoria dos grafos.

Artigos recomendados

Este é um guia para o gráfico na estrutura de dados. Aqui discutimos as terminologias e operações básicas do gráfico na estrutura de dados. Você também pode consultar o seguinte artigo para saber mais -

  1. Perguntas da entrevista sobre estrutura de dados
  2. Modelo de Dados no Cassandra
  3. O que é o Data Mart?
  4. O que é um cientista de dados?

Categoria:

Big Data