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.

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.).

As 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.

Diferentes 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 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^[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	${\displaystyle O(|V|+|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
Adicionar vértice	${\displaystyle O(1)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
Adicionar aresta	${\displaystyle O(1)}$	${\displaystyle O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
Remover vértice	${\displaystyle O(|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
Remover aresta	${\displaystyle O(|V|)}$	${\displaystyle O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
Consulta: os vértices x e y são adjacentes? (Assumindo que suas posições de armazenamento são conhecidas)	${\displaystyle O(|V|)}$	${\displaystyle O(1)}$	${\displaystyle O(|E|)}$
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 |², ou se for necessário verificar rapidamente se existe uma aresta ligando dois vértices.^[5][6]

Referências