Representações de Grafos

Um grafo G = (V, E) contém vértices e arestas. As arestas podem ser direcionadas ou não direcionadas, com ou sem pesos. Um caminho é uma sequência de vértices adjacentes; um caminho simples não repete vértices.

Lista de adjacências

Armazene os vizinhos de saída de cada vértice. O espaço é Θ(V + E), e iterar pelos vizinhos de v custa Θ(out-degree(v)).

static List<List<Integer>> directedGraph(int vertices, int[][] edges) {
    List<List<Integer>> adjacency = new ArrayList<>(vertices);
    for (int v = 0; v < vertices; v++) adjacency.add(new ArrayList<>());
    for (int[] edge : edges) adjacency.get(edge[0]).add(edge[1]);
    return adjacency;
}

Em um grafo não direcionado, adicione as duas orientações de cada aresta. Laços e arestas paralelas são válidos apenas quando o modelo de grafo escolhido os permite.

Matriz de adjacências

Uma matriz V × V usa espaço Θ(V²). Consultas de existência de aresta são Θ(1), enquanto enumerar os vizinhos de um vértice leva Θ(V). É adequada para grafos densos ou algoritmos baseados em matrizes.

Lista de arestas

Uma lista de arestas armazena cada aresta diretamente e usa espaço Θ(E). É conveniente quando os algoritmos principalmente ordenam ou percorrem arestas, como faz o algoritmo de Kruskal.

Escolha da representação

Necessidade	Escolha comum
Percurso de grafo esparso	Lista de adjacências
Teste de aresta em tempo constante em grafo denso	Matriz de adjacências
Ordenar todas as arestas	Lista de arestas
Várias propriedades por aresta	Objetos de aresta ou arrays paralelos compactos

A representação altera as constantes e as operações disponíveis, mas não muda o grafo matemático. Sempre declare se V representa uma quantidade ou um conjunto e se duas orientações armazenadas representam uma única aresta não direcionada.

Exercícios

1. Represente o mesmo grafo direcionado nas três formas.
2. Derive a soma dos graus em um grafo não direcionado.
3. Explique como vértices isolados aparecem em cada representação.