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:
É 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.