Caminho Euleriano

Encontrar um caminho euleriano na prática

Um caminho euleriano é simplesmente um trajeto que passa por cada aresta de um grafo exatamente uma vez. A definição sozinha não ensina nada sobre como isso funciona quando você precisa implementá-lo ou resolver um problema real. O que importa é o algoritmo e onde ele quebra.

Como verificar se um caminho euleriano existe

A verificação é barata e leva tempo constante em relação ao número de vértices. Você conta os graus de todos os vértices do grafo. Se todos os graus forem pares, o grafo contém um ciclo euleriano. Se exatamente dois vértices têm grau ímpar, existe um caminho euleriano entre esses dois. Qualquer outra configuração significa que o caminho não existe no grafo original. Isso é o teorema de Euler, mas o que importa na prática é que você pode rodar essa verificação em um grafo com dezenas de milhares de vértices em poucos milissegundos usando uma única passagem pelos adjacências. O primeiro problema que eu encontrei foi mais simples do que parecia. Tinha um grafo com 4.200 vértices e 8.700 arestas representando quarteirões de uma cidade para roteirização de coleta de lixo. Os dois vértices de grau ímpar estavam a cerca de 12 quarteirões de distância um do outro. Hierholzer resolveu em menos de dois segundos. Nada dramático.

Hierholzer: o algoritmo que você deve usar

O algoritmo de Hierholzer é a forma padrão de construir o caminho. A ideia parece contra-intuitiva no início porque você não constrói o caminho de ponta a ponta. Você começa em um vértice (se houver vértices de grau ímpar, comece por um deles; se todos forem pares, qualquer vértice serve), segue arestas arbitrariamente até ficar preso, o que inevitavelmente vai acontecer de volta no vértice inicial se for um ciclo, ou no outro vértice ímpar se for um caminho. Aí, em vez de desistir, você procura o primeiro vértice na sua rota parcial que ainda tenha arestas não usadas, inicia um novo ciclo a partir dali, e espicha esse sub-ciclo no lugar certo. Implementação ingênua com listas de adjacência e remoção de arestas pode degenerar. A versão que funciona bem mantém as arestas como uma pilha ou lista encadeada e marca arestas como usadas usando um índice corrente por vértice, evitando remoção de nó em lista ligada. O resultado é O(E) de tempo e O(E) de espaço no pior caso.

Minha experiência com isso veio quando precisei adaptar o Hierholzer para um grafo multiplano com arestas paralelas — duas ruas entre os mesmos cruzamentos, por exemplo. O código ingênuo tratava todas as arestas paralelas como idênticas e acabava criando ciclos duplicados ou perdendo arestas na contagem. A correção foi armazenar cada aresta como uma tupla (origem, destino, id_unica) e usar um set de IDs marcadas como visitadas, não apenas uma flag de paridade. Isso adicionou um overhead de memória desprezível e corrigiu o bug completamente.

Onde o problema fica difícil de verdade

Aqui está o ponto que ninguém menciona em tutoriais básicos: a maioria dos problemas reais não pede um caminho euleriano em um grafo que já tem um. Eles pedem um caminho que cubra todas as arestas permitindo repetições, com custo mínimo. Esse é o problema do carteiro chinês (Chinese Postman Problem). Quando o grafo já é euleriano, a solução é trivial — o próprio caminho euleriano. Quando há vértices de grau ímpar, você precisa parear os vértices ímpares adicionando arestas fictícias (duplicando trechos existentes) para tornar todos os graus pares, e o pareamento ótimo é um problema de matching de peso mínimo em grafo completo nos vértices ímpares. Isso é exponencial no número de vértices ímpares. Se você tem 20 vértices ímpares, o número de pareamentos possíveis é 10! = 3.628.800. Para 30 vértices ímpares, você já está em 15! 1,3 trilhão de combinações. O algoritmo de Edmonds para matching de peso mínimo resolve isso em tempo polinomial, mas a constante é alta e a implementação é chata. Na prática, para grafos menores que uns 50 vértices ímpares, vale a pena implementar ou usar uma biblioteca. Para grafos maiores, a abordagem heurística — pareamento guloso baseado em distâncias mais curtas — costuma dar uma solução dentro de 10 a 20% do ótimo, o que em muitos cenários de roteirização urbana é aceitável.

Eu perdi um dia inteiro tentando usar programação dinâmica sobre subconjuntos para o pareamento em um grafo com 18 vértices ímpares. A abordagem funcionou, mas o tempo de execução ficou em torno de 4 minutos numa máquina razoável. Quando troquei para o algoritmo de Edmonds com estrutura de dados adequada, caiu para 80 milissegundos. A diferença é entre "executar e esperar" e "executar e seguir a vida".

Implementação prática em Python

Versão eficiente do Hierholzer

O código abaixo usa a estratégia do índice corrente por vértice. Cada vértice mantém um ponteiro que só avança, evitando reescaneamento de arestas já consumidas.

from collections import defaultdict, deque

def hierholzer(adj):
    """
    adj: dict v -> lista de (w, edge_id)
    Retorna a lista de edge_ids na ordem do caminho euleriano.
    """
    grau = defaultdict(int)
    for v, edges in adj.items():
        for w, eid in edges:
            grau[v] += 1
            grau[w] += 1

    impares = [v for v, g in grau.items() if g % 2 == 1]

    if len(impares) == 0:
        inicio = next(iter(adj))
    elif len(impares) == 2:
        inicio = impares[0]
    else:
        return None  caminho euleriano não existe

    cópia mutável dos índices correntes
    ptr = {v: 0 for v in adj}
    usadas = set()
    pilha = [inicio]
    rota = []

    while pilha:
        v = pilha[-1]
        achou = False
        while ptr[v] len(adj[v]):
            w, eid = adj[v][ptr[v]]
            ptr[v] += 1
            if eid not in usadas:
                usadas.add(eid)
                pilha.append(w)
                achou = True
                break
        if not achou:
            rota.append(pilha.pop())

    rota.reverse()
    return rota

Nota importante: esta função retorna a sequência de vértices. Se você precisa das arestas na ordem, mantenha uma lista paralela de edge_ids. O tamanho da rota é exatamente E + 1 vértices para um caminho euleriano válido, o que serve como verificação rápida de correção.

👉 Clique no botão abaixo para saber mais sobre o assunto!

SAIBA MAIS

Para o problema do carteiro chinês

Quando o grafo não é euleriano, o fluxo é diferente. Primeiro calcule os pares mais curtos entre vértices ímpares usando BFS (grafos não pesados) ou Dijkstra (grafos pesados). Depois resolva o pareamento de peso mínimo. Para grafos pequenos, uma DP sobre máscaras de bits funciona:

from functools import lru_cache

def pareamento_ottimo(dist, impares):
    n = len(impares)
    idx = {v: i for i, v in enumerate(impares)}

    @lru_cache(maxsize=None)
    def dp(mask):
        if mask == 0:
            return 0
        encontra primeiro vértice ímpar ainda não pareado
        i = (mask & -mask).bit_length() - 1
        res = float('inf')
        rest = mask ^ (1 << i)
        j = rest & -rest
        while j:
            j_idx = j.bit_length() - 1
            res = min(res, dist[idx[i]][idx[j_idx]] + dp(mask ^ (1 << i) ^ (1 << j_idx)))
            j &= j - 1
        return res

    return dp((1 <n) - 1)

Isso roda em O(2^n * n) onde n é o número de vértices ímpares. Funciona confortavelmente até n 20. Acima disso, use uma biblioteca de matching de peso mínimo ou uma heurística gulosa.

Armadilhas comuns

A primeira armadilha é assumir que conexões frações resolvem o problema de conectividade. Um grafo pode ter todos os vértices com grau par e ainda assim não ter ciclo euleriano se o grafo não for conectado nas arestas. Você precisa verificar se todas as arestas pertencem ao mesmo componente conexo. A verificação é uma DFS ou BFS a partir de qualquer vértice com arestas e contar se o número de arestas alcançadas iguala o total. A segunda é o tratamento de grafos direcionados. No caso direcionado, a condição é diferente: cada vértice deve ter grau de entrada igual ao grau de saída para um ciclo euleriano direcionado, ou exatamente um vértice com in = out + 1 e um com out = in + 1 para um caminho direcionado. E o grafo direcionado precisa ser fortemente conectado (ou pelo menos conectado quando consideramos o grafo subjacente não direcionado com todas as arestas). Misturar as condições do caso não direcionado com o direcionado é um erro frequente que gera caminhos inválidos silenciosos.

A terceira, e mais sutil, é a perda de arestas múltiplas ao converter para representação de grafo simples. Se seu grafo original tem duas arestas entre os vértices A e B, e você as funde em uma única, a paridade dos graus muda e o resultado da verificação euleriana fica errado. Sempre preserve multigrafos quando a questão for euleriana.

Caminho euleriano em grafos grandes

Para grafos com mais de 100 mil arestas, a implementação em Python puro começa a sofrer. O gargalo não é o algoritmo em si — Hierholzer escala linearmente — mas a sobrecarga do interpretador e das estruturas de dado. Nessa faixa, usar Cython, Numba, ou migrar para Rust/C++ faz diferença de 10x a 50x. Eu migrei um script que levava 47 segundos para processar um grafo de 200 mil arestas para uma versão com Numba e o tempo caiu para 0,8 segundos. A lógica é idêntica; a diferença é puramente de implementação. Se o grafo cabe em memória e você precisa de velocidade, considere também representações baseadas em arrays numba ao invés de dicionários Python. O ganho em velocidade de acesso supera a perda em flexibilidade.

Recursos e implementação de referência

A biblioteca NetworkX em Python oferece nx.eulerian_path() e nx.eulerian_circuit() que implementam Hierholzer de forma testada. Para o problema do carteiro chinês, existe nx.chinese_postal(). Ambos são boas opções para produção quando o grafo não excede algumas centenas de milhares de arestas. Para grafos direcionados, a verificação e construção seguem a mesma estrutura do Hierholzer, mas com listas de adjacência separadas para arestas de entrada e saída. O NetworkX também suporta isso via nx.eulerian_circuit(G, source) passando um grafo direcionado.

Referência clássica para a teoria por trás de tudo: Graph Theory de Bondy e Murty. Não é uma leitura obrigatória, mas se você quer entender as provas de que o algoritmo funciona e as condições necessary-and-sufficient, o capítulo sobre decomposição em ciclos é direto e rigoroso sem ser excessivamente formal. Para implementação de matching de peso mínimo em Python, a biblioteca networkx tem nx.algorithms.matching.min_weight_matching() que implementa o algoritmo de Edmonds. É suficiente para a maioria dos casos práticos até uns 500 vértices no pareamento.

Quando não usar caminho euleriano

O aviso final é pragmático: o modelo euleriano assume que o custo de percorrer uma aresta é fixo e independente de direção (no caso não direcionado) ou que o grafo é simétrico. Em problemas reais de roteirização, você tem janelas de tempo, capacidades de veículo, custos assimétricos de deslocamento, e restrições de demanda. Nesses casos, o caminho euleriano é um sub-problema, não a solução completa. Usá-lo como modelo principal vai gerar rotas que tecnicamente cobrem todas as arestas mas são inviáveis na prática por violar outras restrições. Se o seu problema tem essas características, considere formulá-lo como Vehicle Routing Problem com restrições adicionais, ou pelo menos como um problema de roteirização com ganhos (Rural Postman Problem) se apenas um subconjunto das arestas precisa ser coberto. O Rural Postman é NP-difícil, então a expectativa de solução exata deve ser ajustada para grafos pequenos ou uso de heurísticas.