Representar um grafo: lista e matriz de adjacência

Cada vértice com a sua lista de vizinhos

A lista de adjacência é a representação mais usada na prática. A ideia é direta: para cada vértice, guarde uma lista com os vértices ligados a ele, os seus vizinhos. Se o vértice A se liga a B e a C, a lista de A é [B, C]. Se B se liga só a A, a lista de B é [A]. O grafo inteiro vira um conjunto dessas listinhas, uma por vértice. A grande vantagem é o espaço: você só guarda as ligações que existem de verdade. Num grafo com muitos vértices mas poucas arestas cada, chamado esparso, isso economiza muita memória. E percorrer os vizinhos de um vértice é imediato, porque eles já estão listados ali, prontos. É por isso que redes sociais, com milhões de pessoas mas poucas amizades por pessoa em relação ao total, quase sempre usam lista de adjacência.

grafo <- {
  "A": ["B", "C"],
  "B": ["A", "D"],
  "C": ["A", "D"],
  "D": ["B", "C"]
}
// vizinhos de A:
escreva(grafo["A"])   // ["B", "C"]
// A e D sao vizinhos? procurar D na lista de A:
escreva("D" está em grafo["A"])   // falso (A liga a B e C, nao a D)

Lista de adjacência: cada vértice aponta para a sua lista de vizinhos. Simples, econômica e rápida para percorrer vizinhos.

A grade de conexões: a matriz de adjacência

A matriz de adjacência usa a estrutura que você estudou no curso intermediário: uma matriz, a grade de linhas e colunas. Numere os vértices de 0 em diante e monte uma grade quadrada com um vértice por linha e o mesmo por coluna. Na célula da linha A com a coluna B você escreve 1 se existe aresta de A para B, e 0 se não existe. Para saber se dois vértices são vizinhos, basta olhar uma célula: matriz[A][B]. Essa consulta é instantânea, um único acesso, e é a maior vantagem da matriz. O preço é o espaço: uma grade de N vértices por N vértices ocupa N ao quadrado células, mesmo que quase todas sejam zero. Para um grafo com muitas ligações (denso) e poucos vértices, a matriz compensa. Para um grafo esparso e grande, ela desperdiça memória com um mar de zeros.

grafo <- {
  "A": ["B", "C"],
  "B": ["A", "C", "D"],
  "C": ["A", "B"],
  "D": ["B"]
}
vizinhos <- grafo["B"]
escreva(tamanho(vizinhos))

Qual das duas escolher

A escolha depende de duas coisas: o tamanho do grafo e a sua densidade. Se o grafo é esparso, com poucas arestas por vértice, a lista de adjacência quase sempre vence: economiza memória e é ótima para percorrer vizinhos, que é o que a maioria dos algoritmos faz. Se o grafo é denso, com quase todos os pares ligados, ou se o programa precisa checar muitas vezes e rápido se dois vértices específicos são vizinhos, a matriz de adjacência compensa a memória extra com consultas de um passo. Na dúvida, e na prática do dia a dia, a lista de adjacência é a escolha padrão, porque a maioria dos grafos reais é esparsa e grande. A matriz aparece mais em grafos pequenos, densos ou em algoritmos que dependem de olhar pares direto. Saber que as duas existem, e o que cada uma custa, já resolve a decisão na hora certa.