Lista de Adjacência
A lista de adjacência é uma representação computacional de grafos baseada em listas ligadas (ou estruturas equivalentes).
Cada vértice do grafo mantém uma lista contendo todos os
vértices adjacentes a ele.
- Vértice: nó principal da estrutura
- Link: aponta de um vértice para outro vértice adjacente
- Cada elemento: vértice + lista de links
Essa representação é especialmente eficiente para grafos esparsos e é a mais usada em implementações práticas.
Exemplo — Grafo orientado e lista de adjacência
Lista de adjacência correspondente ao grafo:
A → B → C → D → NULL
B → C → E → NULL
C → D → NULL
D → E → NULL
E → NULL
Cada linha representa um vértice e os elementos à direita são os vértices alcançáveis por uma aresta de saída.
Diferente das matrizes, a lista de adjacência armazena apenas as conexões existentes,
reduzindo o consumo de memória.