Mostrar código-fonte de Grafo (tipo de dado abstrato)

[[Ficheiro:Directed.svg|miniaturadaimagem|125x125px|Um grafo com três vértices e três arestas.]]
Em [[ciência da computação]], um '''grafo''' é um [[tipo abstrato de dado]]s que destina-se a implementar os conceitos [[matemáticos]] de [[grafo não-direcionado]] e [[Grafo orientado|gráfico direcionado]], especificamente no campo da [[teoria dos grafos]].

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&nbsp;'' linhas dirigidas'' para um [[grafo direcionadcode> redundantes ([[Ajuda:Erros nas referências#redundant parameters|ajuda]])
o]]. Os vértices podem ser parte do grafo, ou podem ser entidades externas representadas por índices inteiros ou [[Referência (ciência da computação)|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 ==
As operações básicas fornecidas por uma estrutura de dados ''G '' de tipo grafo geralmente incluem:<ref name="gt-ops">See, e.g. </ref>
* <code>adjacencia</code>(''G'', ''x'', ''y''): testa se existe uma aresta do vértice ''x'' para o vértice ''y'';
* <code>vizinhos</code>(''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'';
* <code>adiciona_vertice</code>(''G'', ''x''): adiciona o vértice ''x'', se ele não estiver lá;
* <code>remove_vertice</code>(''G'', ''x''): remove o vértice ''x'', se este existir;
* <code>adiciona_aresta</code>(''G'', ''x'', ''y''): adiciona a aresta do vértice ''x'' para o vértice ''y'', se ela não existir;
* <code>remove_aresta</code>(''G'', ''x'', ''y''): remove a aresta do vértice ''x'' para o vértice ''y'', se esta existir;
* <code>get_valor_vertice</code>(''G'', ''x''): retorna o valor associado ao vértice ''x'';
* <code>set_valor_vertice</code>(''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:
* <code>get_valor_aresta</code>(''G'', ''x'', ''y''): retorna o valor associado à aresta (''x'', ''y'');
* <code>set_valor_aresta</code>(''G'', ''x'', ''y'', ''v''): define o valor associado à aresta (''x'', ''y'') para ''v''.

== Representações ==
Diferentes estruturas de dados para representação de grafos são utilizados na prática:
; [[Lista de adjacência]]<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 528–529; {{Harvtxt|Goodrich|Tamassia|2015}}, pp. 361-362.</ref>
: 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&nbsp; vértices incidentes.
; [[Matriz de adjacência]]<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 529–530; {{Harvtxt|Goodrich|Tamassia|2015}}, p.&nbsp;363.</ref>
: Uma matriz bidimensional, na qual as linhas representam os vértices de origem e as colunas representam os vértices de 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]]<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p.&nbsp;531.</ref>
: Uma matriz bidimensional [[Matriz booliana|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 [[Complexidade de Tempo|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|data=agosto de 2017}}
O custo das arestas que não estão presentes são considerados ∞.
{| class="wikitable" style="margin-bottom: 10px;"
!
!Lista de adjacência<br>
!Matriz de adjacência<br>
!Matriz de incidência<br>
|-
|Espaço
| <math>O(|V|+|E|)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
|-
| Adicionar vértice<br>
| <math>O(1)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
|-
| Adicionar aresta<br>
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(|V|\cdot|E|)</math>
|-
| Remover vértice<br>
| <math>O(|E|)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
|-
| Remover aresta<br>
| <math>O(|V|)</math>
| <math>O(1)</math>
| <math>O(|V|\cdot|E|)</math>
|-
|Consulta: os vértices x e y são adjacentes? (Assumindo que suas posições de armazenamento são conhecidas)
| <math>O(|V|)</math>
| <math>O(1)</math>
| <math>O(|E|)</math>
|-
| 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'' |<sup>2</sup>, ou se for necessário verificar rapidamente se existe uma aresta ligando dois vértices.<ref name="clrs">{{Citation|título=[[Introduction to Algorithms]]|ano=2001|último =Cormen|último2 =Leiserson|último3 =Rivest|último4 =Stein|primeiro =Thomas H.|primeiro2 =Charles E.|primeiro3 =Ronald L.|primeiro4 =Clifford|autorlink =Thomas H. Cormen|authorlink2=Charles E. Leiserson|authorlink3=Ronald L. Rivest|authorlink4=Clifford Stein|páginas=527–531|capítulo=Section 22.1: Representations of graphs|edição=Second|publicado=MIT Press and McGraw-Hill|isbn=0-262-03293-7}} {{ISBN|0-262-03293-7}}</ref><ref name="gt">{{Citation|título=Algorithm Design and Applications|ano=2015|último1 =Goodrich|último2 =Tamassia|primeiro1 =Michael T.|primeiro2 =Roberto|autorlink1 =Michael T. Goodrich|autorlink2 =Roberto Tamassia|páginas=355–364|publicação=Section 13.1: Graph terminology and representations|publicado=Wiley}}.</ref>
{{portal|Tecnologia da informação}}

{{Referências}}

{{Estrutura de dados}}

[[Categoria:!Páginas com citações e parâmetros redundantes]]
[[Categoria:Teoria dos grafos]]
[[Categoria:Tipos abstratos de dados]]