Estrutura de dados do gráfico e Algorithms (Exemplo)

O que é um gráfico na estrutura de dados?

Um gráfico é uma estrutura de dados não linear que consiste em vértices e arestas, onde os vértices contêm as informações ou dados, e as arestas funcionam como um link entre pares de vértices.

É usado para resolver problemas reais, como encontrar a melhor rota para o local de destino e a rota para telecomunicações e redes sociais. Os usuários são considerados um nó no gráfico e os fios são as arestas que conectam os usuários.

Se as arestas são representadas como E e os vértices são representados como V, então o grafo G pode ser escrito como o conjunto de vértices e arestas, como G (V, E)

Exemplo de gráfico em estrutura de dados

Aqui está um exemplo simples de estrutura de dados gráfica:

Exemplo de gráfico em estrutura de dados

É um gráfico simples e não direcionado (um tipo de gráfico). Aqui o conjunto de vértices é: {A, B, C,D,E,F}. Dois vértices criam uma aresta. Por exemplo, A e B estão ligados por uma aresta. No entanto, A e F não estão ligados a nenhuma aresta.

Terminologias gráficas em estrutura de dados

A seguir estão alguns termos importantes usados ​​na estrutura de dados do gráfico:

INVERNO Descrição
Vértice Todo elemento de dados é chamado de vértice ou nó. Na imagem acima, A, B, C, D e E são os vértices.
Borda (arco) Os links de conexão entre dois nós ou vértices são chamados de aresta (arco). Possui duas extremidades e é representado como (startingVertex, endVertex).
Borda não direcionada É uma borda bidirecional.
Borda direcionada É uma borda unidirecional.
Borda ponderada Uma vantagem com valor.
Grau No gráfico, o número de arestas conectadas a um vértice é chamado de grau.
Grau de graduação O número total de arestas de entrada conectadas a um vértice.
Outdegree O número total de arestas de saída conectadas a um vértice.
Circuito automático Uma aresta é chamada de auto-loop se suas duas extremidades coincidem.
Adjacência Os vértices são considerados adjacentes se uma aresta estiver conectada.

Tipos de gráficos na estrutura de dados

Aqui está a lista dos mais comuns tipos de gráficos na estrutura de dados:

  • Gráfico direcionado
  • Gráfico não direcionado
  • Gráfico ponderado
  • Gráfico bidirecional
  • Gráfico Infinito
  • Gráfico Nulo
  • Gráfico Trivial
  • Multigráfico
  • Gráfico Completo
  • Gráfico Conectado
  • Gráfico Cíclico
  • Gráfico Acíclico Direcionado (DAG)
  • Gráfico de Ciclo
  • Gráfico Bipartido
  • Gráfico de Euler
  • Gráfico de Hamilton

Aplicações da estrutura de dados gráfica

Um gráfico tem muitos casos de uso. Existem muitos algoritmos que usam muito gráficos. Aqui estão algumas das aplicações do gráfico:

  • O Google Maps usa gráficos para encontrar a intersecção de duas estradas e calcular a distância entre dois locais.
    Por exemplo, nos Dijkstra, para encontrar a distância mais curta entre o local de origem e de destino.
  • O Facebook usa gráficos para encontrar amigos em comum dos usuários. Seu algoritmo considera cada usuário como um nó de um grafo.
  • Para alocação de recursos, é utilizado DAG (Direct Acíclico Graph). Ele verifica a dependência dos recursos.
  • O Google Search Engine usa gráficos para criar a classificação dos sites.
  • Um dispositivo de mapeamento usa a estrutura de dados do gráfico.
  • router e o protocolo t usa o gráfico para aprender o caminho do caminho de destino.