Estrutura de dados do gráfico e Algorithms (Exemplo)
Sarah Chen
⚡ Resumo Inteligente
Uma estrutura de dados em grafo é uma coleção não linear de vértices e arestas, onde cada aresta conecta um par de vértices. Os grafos modelam redes do mundo real, como mapas, conexões sociais e páginas da web, e suportam muitos algoritmos poderosos.
O que é um gráfico na estrutura de dados?
Um grafo é 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 uma ligação entre um par de vértices.
É utilizado para resolver problemas do mundo real, como encontrar a melhor rota para um destino e o roteamento para telecomunicações e redes sociais. Os usuários são considerados nós no grafo, e os fios são as arestas que os conectam.
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 uma estrutura de dados em forma de grafo:
Trata-se de um grafo simples não direcionado (um tipo de grafo). O conjunto de vértices é: {A, B, C, D, E, F}. Dois vértices formam uma aresta. Por exemplo, A e B estão conectados por uma aresta. No entanto, A e F não estão conectados por nenhuma aresta.
Terminologias gráficas em estrutura de dados
A seguir, apresentamos alguns termos importantes usados na estrutura de dados de grafos:
| INVERNO | Descrição |
|---|---|
| Vértice | Cada 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) | As ligações entre dois nós ou vértices são chamadas de arestas (arcos). Elas têm duas extremidades e são representadas como (vérticeInicial, vérticeFinal). |
| Borda não direcionada | É uma borda bidirecional. |
| Borda direcionada | É uma borda unidirecional. |
| Borda ponderada | Uma aresta com um valor associado. |
| Grau | Em um grafo, 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 | Diz-se que dois vértices são adjacentes se uma aresta os conecta. |
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
Como representar um grafo em uma estrutura de dados?
Um grafo é geralmente armazenado na memória usando uma de duas representações. A escolha afeta a quantidade de memória que o grafo utiliza e a velocidade de execução das operações comuns.
- Matriz de adjacência: Uma matriz bidimensional V × V onde a célula [i][j] é 1 (ou o peso da aresta) se existir uma aresta entre o vértice i e o vértice j, e 0 caso contrário. Permite a busca de arestas em O(1), mas usa espaço O(V²), tornando-a ideal para grafos densos.
- Lista de adjacências: Uma matriz de listas onde cada vértice armazena uma lista de seus vértices vizinhos. Ela usa espaço O(V + E) e é eficiente para grafos esparsos, razão pela qual a maioria dos grafos do mundo real a utiliza.
Você pode ler mais sobre isso em Lista de adjacência e representação matricial de um grafo tutorial.
Aplicações da estrutura de dados gráfica
Um grafo tem muitas aplicações. Existem muitos algoritmos que utilizam grafos. Aqui estão algumas das aplicações de grafos:
- Google Os mapas utilizam gráficos para encontrar a intersecção de duas estradas e calcular a distância entre dois locais. Por exemplo, Dijkstra, para encontrar a menor distância entre a localização de origem e a de destino.
- O Facebook usa grafos para encontrar os amigos em comum dos usuários. Seu algoritmo considera cada usuário como um nó de um grafo.
- Para a alocação de recursos, utiliza-se um DAG (Grafo Acíclico Direcionado). Ele verifica a dependência entre os recursos.
- O Google Os mecanismos de busca utilizam gráficos para criar o ranking dos sites.
- Um mapaping O dispositivo utiliza a estrutura de dados em forma de grafo.
- A router e seu protocolo usam o grafo para aprender o caminho até o destino.
