Representando um Grafo

No tópico anterior, você viu alguns conceitos e definições básicas de grafos. Mas uma questão que você deve ter feito é: como representar um grafo em um computador?

Neste tópico, iremos discutir as duas formas mais usuais de representação de grafos em um computador: a lista de adjacência e a matriz de adjacência. Além disso, discutiremos a complexidade computacional de ambas as representações para as seguintes operações:

• add(u, v): adicionar uma aresta e = (u, v);
• delete(u, v): remover uma aresta e = (u, v);
• edge(u, v): checar se v é vizinho de u;
• vizinhança(u): listar os vértices que são vizinhos de u;
• complexidade espacial: quantidade de memória para representar o grafo.

Matriz de Adjacência

A matriz de adjacência consiste de uma matriz com duas dimensões e estática , tal que a -ésima linha de representa o i-ésimo vértice de , , da mesma forma, cada -ésima coluna de representa o -ésimo vértice de G, .

Então definimos cada posição da matriz M[i][j] da seguinte maneira:

para todo . Note que, para grafos não direcionados, a matriz é simétrica, ou seja, M[i][j] = M[j][i], pois podemos usar a aresta em ambos os sentidos. Vale ressaltar que a definição dada acima é válida para grafos não valorados, ou seja, grafos que não possui peso em suas arestas, caso o grafo seja valorado na arestas como um valor então ao invés de atribuir 1 para a posição da matriz, iremos atribuir o valor da aresta.