Grafo (tipo de dado abstrato)
Em ciência da computação, um grafo é um tipo abstrato de dados que destina-se a implementar os conceitos matemáticos de grafo não-direcionado e gráfico direcionado, especificamente no campo da teoria dos grafos.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Directed.svg/125px-Directed.svg.png)
Um grafo consiste de um conjunto finito (e, possivelmente, mutável) de vértices ou nós ou pontos, com um conjunto de pares não ordenados destes vértices para um grafo não-direcionado, ou um conjunto de pares ordenados para um grafo direcionado. Esses pares são conhecidos como arestas, arcos ou linhas para um grafo não-direcionado e como setas, arestas dirigidas, arcos dirigidos ou linhas dirigidas para um [[grafo direcionadcode> redundantes (ajuda)o]]. Os vértices podem ser parte do grafo, ou podem ser entidades externas representadas por índices inteiros ou referências.
Uma estrutura de dados do tipo grafo pode também associar a cada aresta algum peso, como um rótulo simbólico ou um atributo numérico (custo, capacidade, comprimento, etc.).
Operações
editarAs operações básicas fornecidas por uma estrutura de dados G de tipo grafo geralmente incluem:[1]
adjacencia
(G, x, y): testa se existe uma aresta do vértice x para o vértice y;vizinhos
(G, x): apresenta a lista de todos os vértices y tais que existe uma aresta do vértice x para o vértice y;adiciona_vertice
(G, x): adiciona o vértice x, se ele não estiver lá;remove_vertice
(G, x): remove o vértice x, se este existir;adiciona_aresta
(G, x, y): adiciona a aresta do vértice x para o vértice y, se ela não existir;remove_aresta
(G, x, y): remove a aresta do vértice x para o vértice y, se esta existir;get_valor_vertice
(G, x): retorna o valor associado ao vértice x;set_valor_vertice
(G, x, v): define o valor associado ao vértice x para v.
Estruturas que associam valores para as arestas, normalmente, também fornecem as seguintes operações:
get_valor_aresta
(G, x, y): retorna o valor associado à aresta (x, y);set_valor_aresta
(G, x, y, v): define o valor associado à aresta (x, y) para v.
Representações
editarDiferentes estruturas de dados para representação de grafos são utilizados na prática:
- Lista de adjacência[2]
- Os vértices são armazenadas como registros ou objetos, e cada vértice armazena uma lista de vértices adjacentes. Esta estrutura de dados permite o armazenamento de dados adicionais sobre os vértices. Dados adicionais podem ser armazenados se as arestas forem armazenadas também como objetos, neste caso cada vértice armazena as suas arestas incidentes e cada aresta armazena os seus vértices incidentes.
- Matriz de adjacência[3]
- Uma matriz bidimensional, na qual as linhas representam os vértices fonte e colunas representam os vértices destino. Dados sobre as arestas e os vértices devem ser armazenados externamente. Apenas o custo de uma aresta pode ser armazenado entre cada par de vértices.
- Matriz de incidência[4]
- Uma matriz bidimensional Booleana, na qual as linhas representam os vértices e as colunas representam as arestas. As entradas de indicam se o vértice de uma linha é incidente à aresta de uma coluna.
A tabela a seguir fornece o custo em tempo de complexidade de executar várias operações em grafos, para cada uma dessas representações, sendo |V | o número de vértices e |E | o número de arestas.[carece de fontes]
O custo das arestas que não estão presentes são considerados ∞.
Lista de adjacência |
Matriz de adjacência |
Matriz de incidência | |
---|---|---|---|
Espaço | |||
Adicionar vértice |
|||
Adicionar aresta |
|||
Remover vértice |
|||
Remover aresta |
|||
Consulta: os vértices x e y são adjacentes? (Assumindo que suas posições de armazenamento são conhecidas) | |||
Remarcações | Lento para remover vértices e arestas, porque precisa encontrar todos os vértices ou arestas. | Lento para adicionar ou remover vértices, porque a matriz deve ser redimensionada/copiada. | Lento para adicionar ou remover vértices e arestas, porque a matriz precisa ser redimensionada/copiada |
Listas de adjacência são geralmente desejadas porque elas são eficientes em representar grafos esparsos. Uma matriz de adjacências é preferível se o gráfico é denso, quando o número de arestas |E | é proximo do número de vértices quadrados, |V |2, ou se for necessário verificar rapidamente se existe uma aresta ligando dois vértices.[5][6]
Referências
- ↑ See, e.g.
- ↑ Cormen et al. (2001), pp. 528–529; Goodrich & Tamassia (2015), pp. 361-362.
- ↑ Cormen et al. (2001), pp. 529–530; Goodrich & Tamassia (2015), p. 363.
- ↑ Cormen et al. (2001), Exercise 22.1-7, p. 531.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), «Section 22.1: Representations of graphs», Introduction to Algorithms, ISBN 0-262-03293-7 Second ed. , MIT Press and McGraw-Hill, pp. 527–531 ISBN 0-262-03293-7
- ↑ Goodrich, Michael T.; Tamassia, Roberto (2015), «Algorithm Design and Applications», Wiley, Section 13.1: Graph terminology and representations, pp. 355–364.