Introdução a Grafos

O que é, em duas palavras

Um grafo é um par: um conjunto de vértices (os pontos) e um conjunto de arestas (as ligações entre eles). Só isso. A riqueza vem das variações:

E o vocabulário mínimo, que aparece em todo enunciado:

• Grau de um vértice: quantas arestas saem dele. Em grafo dirigido, separa-se em grau de entrada e de saída.
• Caminho: sequência de vértices ligados por arestas.
• Ciclo: caminho que volta ao ponto de partida. Árvore é justamente o grafo sem ciclo.
• Conexo: existe caminho entre qualquer par de vértices. Se não, o grafo tem componentes separados.
• Denso e esparso: muitas ou poucas arestas em relação ao máximo possível. Esta palavra decide a próxima seção.

Guardar o grafo: as duas formas

Existem dois jeitos de representar as arestas, e a escolha entre eles é a primeira decisão de projeto.

A matriz de adjacência é uma tabela V por V em que a célula [i][j] diz se existe aresta de i para j. A lista de adjacência é um vetor de listas: para cada vértice, quem são os vizinhos dele.

# matriz: V x V, sempre
matriz = [[0, 1, 0, 0],
          [1, 0, 1, 0],
          [0, 1, 0, 1],
          [0, 0, 1, 0]]

# lista: só o que existe
lista = {0: [1], 1: [0, 2], 2: [1, 3], 3: [2]}

Comece no preset esparso e olhe a matriz: quase tudo é zero. Cada zero é memória reservada para uma aresta que não existe. Agora clique nas células para ligar arestas e veja o desenho e a lista acompanharem, e o contador de "células em zero" cair.

Depois troque para completo e compare os dois custos: com o grafo cheio, a matriz para de desperdiçar.

Por fim, ligue o modo dirigido e clique numa célula: agora só ela acende, enquanto no modo não dirigido a célula espelhada acompanhava. É a prova de uma coisa boa de saber: num grafo não dirigido, metade da matriz é cópia da outra metade, e a lista guarda cada aresta duas vezes justamente por isso.

Qual escolher, e por quê

A conta é direta. A matriz custa V² células, existam arestas ou não. A lista custa V + 2E (ou V + E se for dirigido), porque só guarda o que existe.

Cada uma ganha em uma coisa. A matriz responde "existe aresta?" em tempo constante, e a lista percorre vizinhos sem olhar quem não é vizinho.

Na prática, a lista vence quase sempre, por um motivo de escala: com um milhão de vértices, a matriz pediria 10¹² células, algo em torno de um terabyte. Não é lento, é impossível. Já a lista guarda só as arestas reais.

Em Python, a lista de adjacência costuma ser um dicionário de listas, e o defaultdict evita metade dos casos de borda:

from collections import defaultdict

g = defaultdict(list)
for u, v in arestas:
    g[u].append(v)
    g[v].append(u)      # tire esta linha e o grafo vira dirigido

Essa única linha comentada é a diferença entre os dois mundos, e vale ler o código de qualquer solução de grafo procurando por ela.

O grafo que você não desenhou

Aqui está a ideia que mais rende em problema de entrevista: você quase nunca recebe um grafo. Você recebe outra coisa e precisa enxergar o grafo dentro dela.

O caso mais comum é a grade. Uma matriz de células é um grafo em que cada célula é um vértice e as vizinhas (acima, abaixo, esquerda, direita) são as arestas. Você não constrói lista de adjacência nenhuma: a vizinhança é calculada na hora.

DIRECOES = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def vizinhos(grade, i, j):
    for di, dj in DIRECOES:
        ni, nj = i + di, j + dj
        if 0 <= ni < len(grade) and 0 <= nj < len(grade[0]):
            yield ni, nj

Com isso, "quantas ilhas existem neste mapa" vira "quantos componentes conexos tem este grafo", e "menor número de passos até a saída do labirinto" vira BFS. Metade dos problemas de grade do LeetCode é grafo disfarçado.

A mesma leitura serve para outras coisas:

• Palavras: cada palavra é um vértice, e existe aresta se elas diferem por uma letra (é o Word Ladder).
• Estados de um jogo: cada configuração do tabuleiro é um vértice, cada jogada é uma aresta.
• Dependências: cada tarefa é um vértice, cada "A precisa de B" é uma aresta dirigida. É o ordenamento topológico.
• Rotas de um servidor web: cada segmento de URL é um vértice, e resolver a rota é caminhar no grafo.

Onde ficam os ciclos, e por que isso importa

Uma diferença prática entre grafo e árvore muda o código de todo percurso: no grafo existe ciclo, então você pode voltar a um vértice já visitado e girar para sempre.

A solução é uma linha, e ela é obrigatória:

visitados = set()

def dfs(u):
    if u in visitados:
        return
    visitados.add(u)
    for v in g[u]:
        dfs(v)

Numa árvore, esse set não existe, porque a estrutura garante que você nunca volta. Num grafo, esquecer dele é recursão infinita. É a diferença mais importante entre os percursos que você já conhece e os de DFS e BFS em grafos, que é exatamente o próximo tópico.

Como praticar

Comece pelos problemas que pedem para você enxergar o grafo antes de percorrer. Number of Islands é a grade como grafo e componentes conexos; Flood Fill é a mesma ideia com pintura. Find if Path Exists in Graph é a versão mais direta possível, e serve para você escrever sua primeira lista de adjacência do zero.

Depois, Clone Graph é ótimo por um motivo diferente: ele obriga a lidar com ciclo de verdade, porque copiar ingenuamente entra em laço infinito, e a saída é um mapa de "original para cópia" que faz o papel do conjunto de visitados.

Se quiser treinar a representação em si, pegue qualquer problema resolvido com lista de adjacência e reescreva com matriz. A solução vai ficar mais curta em um ponto e absurdamente cara em outro, e sentir isso na mão vale mais que a tabela desta página.

A partir daqui, o caminho é DFS e BFS em Grafos, que traz os dois percursos com o detalhe dos visitados, e depois os algoritmos de caminho mínimo: Dijkstra para pesos não negativos e Bellman-Ford para quando existe peso negativo.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 1:46:55.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.