O que é um passeio em grafos
Um passeio em grafos consiste de uma sequência de vértices e arestas que se sucedem de maneira válida segundo as regras da teoria dos grafos. Na prática, você parte de um vértice inicial, percorre arestas ligando vértices consecutivos, e o passeio termina quando você não tem mais arestas para seguir ou decide parar. A definição formal diz que um passeio é uma alternância v0, e1, v1, e2, v2, ..., ek, vk onde cada ei conecta vi-1 a vi. Não há restrição sobre repetir vértices ou arestas — isso é justamente o que diferencia um passeio de outros conceitos mais restritos, como trilhas ou caminhos. Quando eu estava otimizando um rotas de entrega para uma empresa de logística há alguns anos, precisei modelar o problema usando passeios em grafos. O cenário real era mais confuso do que a teoria sugere: os vértices eram esquinas, as arestas eram quarteirões com restrições de sentido, e havia horários de funcionamento que tornavam certas arestas indisponíveis em certos períodos. A primeira versão do algoritmo gerava passeios válidos matematicamente, mas algumas rotas passavam pela mesma esquina três vezes em cinco minutos, o que era impossível na prática porque o motorista precisava de tempo de travessia. A solução foi adicionar um peso temporal às arestas e validar cada transição contra um horário de chegada mínimo. Isso transformou o passeio teórico em um passeio viável operacionalmente.
Passeio em grafos consiste de uma sequência bem definida
A definição exata importa porque pequenas diferenças conceituais geram implementações erradas. Um passeio permite repetição ilimitada de vértices e arestas. Uma trilha proíbe repetição de arestas, mas permite repetir vértices. Um caminho proíbe repetição de vértices, o que automaticamente proíbe repetição de arestas. Um ciclo é um passeio que começa e termina no mesmo vértice. Um ciclo simples é um ciclo sem repetição de vértices internos. Esses quatro conceitos são frequentemente confundidos em exercícios acadêmicos e em implementações produção também. O comprimento de um passeio é o número de arestas percorridas. Em grafos ponderados, fala-se em custo ou peso total do passeio, que é a soma dos pesos das arestas incluídas. Se o grafo tem n vértices, um passeio pode ter comprimento arbitrário — não há limite superior teórico. Isso é útil para modelar situações onde você volta várias vezes ao mesmo ponto, mas é perigoso se você espera que o algoritmo termine em tempo razoável sem uma estratégia de poda ou limites adicionais.
Como representar e percorrer passeios na prática
A representação mais comum de um grafo para fins de percurso é a lista de adjacência. Para cada vértice u, você armazena uma lista de pares (v, peso) indicando que existe uma aresta de u para v com determinado peso. Em grafos não direcionados, cada aresta aparece duas vezes, uma em cada direção. Em grafos direcionados, apenas na direção indicada. A matriz de adjacência também funciona, especialmente para grafos densos, mas consome O(n²) de memória e é menos eficiente para iteração rasa de vizinhos. Para gerar um passeio, o algoritmo mais básico é uma busca em profundidade (DFS) simples. Você mantém um vetor visitado opcional, inicia em um vértice fonte, e recursivamente explora vizinhos. A diferença crucial é que, para passeio, você NÃO marca vértices como permanentemente visitados — ou marca apenas para controle de estocagem, mas permite revisitá-los. Se quiser evitar ciclos infinitos em grafos com ciclos, imponha um limite máximo de comprimento ou rastreie arestas já percorridas dependendo do tipo de passeio desejado.
Em minhas experiências com grafos de redes de telecomunicação, precisei gerar passeios que cobrissem todas as arestas de um subgráfico para inspeção de infraestrutura. O problema era que o grafo tinha 847 vértices e 1.203 arestas direcionais, e muitos vértices tinham grau ímpar. Passeios que cobrem todas as arestas exatamente uma vez são passeios eulerianos, e a condição necessária e suficiente para existência em grafo conexo direcionado é que todo vértice tenha grau de entrada igual ao grau de saída. Quando essa condição não era satisfeita, eu precisava adicionar arestas fantasmas (duplicatas) nos vértices desbalanceados para criar um multigrafo euleriano, resolver o passeio euleriano no multigrafo, e então mapear de volta para o grafo original. Esse procedimento de eulerianização reduziu o tempo de inspeção de 6 horas para 45 minutos em campo.
Passeios eulerianos e hamiltonianos: onde a coisa fica interessante
Passeios eulerianos tratam de arestas. Um passeio euleriano percorre cada aresta do grafo exatamente uma vez. Se começa e termina no mesmo vértice, é um ciclo euleriano. A caracterização de Euler data de 1736 e é surpreendentemente simples: para grafos conexos não direcionados, todos os vértices devem ter grau par para existência de ciclo euleriano; exatamente dois vértices de grau ímpar permitem passeio euleriano (não ciclo), sendo esses dois vértices necessariamente o início e o fim. Para grafos direcionados, grau de entrada deve igualar grau de saída para ciclo, e no máximo um vértice pode ter entrada = saída + 1 (início) e um vértice saída = entrada + 1 (fim) para passeio aberto. Passeios hamiltonianos tratam de vértices. Um passeio hamiltoniano visita cada vértice exatamente uma vez. Diferentemente do caso euleriano, não existe caracterização simples e necessária e suficiente para existência de passeio hamiltoniano. O problema de decidir se um grafo arbitrário possui tal passeio é NP-completo. Isso significa que, na prática, você não vai encontrar um algoritmo polinomial que resolva isso para todos os grafos. Algoritmos heurísticos funcionam bem para grafos com estrutura específica — grafos densos, grafos com propriedade de Dirac (grau mínimo n/2 garante ciclo hamiltoniano), ou grafos com propriedade de Ore — mas falham miseravelmente em instâncias mal-comportadas.
👉 Clique no botão abaixo para saber mais sobre o assunto!
O erro comum que vejo em implementações é confundir os dois problemas. Alguém precisa visitar todas as cidades (vértices) uma vez e tenta usar Hierholzer, que é algoritmo euleriano para arestas. O resultado é um passeio que cobre todas as arestas mas pode pular cidades ou repetir outras. A distinção prática é simples de lembrar se você pensar assim: euleriano = cobrar pedágio em cada estrada uma vez; hamiltoniano = passar por cada cidade uma vez.
Implementação prática com validação de restrições reais
Uma implementação robusta de geração de passeios em grafos precisa lidar com pelo menos cinco tipos de restrição que aparecem em cenários reais. Primeiro, restrições de capacidade: algumas arestas têm limite de fluxo e não podem ser usadas repetidamente dentro de uma janela temporal. Segundo, restrições temporais: certos vértices só são acessíveis em janelas de horário. Terceiro, restrições de custo: passeios com custo total acima de um limiar precisam ser rejeitados ou priorizados diferentemente. Quarto, restrições de preferência: algumas arestas ou vértices têm penalidade ou bônus associado. Quinto, restrições de consistência: o passeio final precisa satisfazer invariantes globais, como retorno ao ponto de partida ou visitação de um subconjunto obrigatório de vértices. Para o caso específico que mencionei anteriormente de rotas de entrega com janelas de horário, a implementação usava uma varianteda DFS com backtracking guiado por heurística A*. O grafo era construído dinamicamente: a cada estado da busca, as arestas disponíveis eram filtradas pelo horário atual mais o tempo de viagem. O heuristicamente usava a distância euclidiana em linha reta até o próximo destino obrigatório não visitado, que era admissível mas não consistente em alguns cenários porque as janelas de horário podiam tornar o caminho mais longo na prática do que a linha reta sugere. Esse desvio entre heurística e realidade causava até 23% de esforço computacional extra em grafos com muitas restrições temporais apertadas. A correção foi usar uma heurística mais pessimista que considerava o tempo mínimo de espera nas janelas, o que reduziu o esforço extra para cerca de 7%.
Limitações e quando não usar passeios em grafos
Passeios em grafos são uma ferramenta poderosa mas têm limitações sérias que tornam sua aplicação cega perigosa. A principal limitação é a explosão combinatória: o número de passeios possíveis em um grafo com n vértices e grau médio d é exponencial em n. Mesmo com poda agressiva, grafos com mais de algumas centenas de vértices e estrutura densa tornam a enumeração completa impraticável. Para esses casos, você precisa de aproximações, amostragem, ou formulações de otimização diferente. Outra limitação importante é que passeios em grafos clássicos assumem grafo estático. Em sistemas dinâmicos onde arestas aparecem e desaparecem, ou onde pesos mudam com o tempo, o modelo tradicional precisa ser estendido para grafos temporais. A complexidade aumenta significativamente e muitos algoritmos eulerianos e hamiltonianos clássicos não se generalizam diretamente. Grafos temporais exigemnoções de Tempo-respecting paths, que são um tópico de pesquisa ativo com poucas soluções prontas para produção.
Se o seu problema envolve restrições de recursos multidimensionais — capacidade de combustível, tempo do motorista, janelas de entrega múltiplas, restrições de compatibilidade de carga — passeios em grafos puros vão te levar a uma implementação que funciona para instâncias pequenas mas quebra em escala. Nesse cenário, formulações de programação inteira mista (MIP) ou search local com constraints específicas costumam ser mais adequadas. Passeios em grafos ainda servem como sub-rotina ou base conceitual, mas raramente são a solução completa.
Recursos para aprofundamento
Para quem quer implementar passeios em grafos com solidez, a referência clássica é o livro Graph Theory de Diestel, que cobre teoria pura com rigor. Para aspectos algorítmicos, Algorithm Design de Kleinberg e Tardos tem capítulos bons sobre flusso e emparelhamento que se conectam diretamente com passeios eulerianos. Para implementações práticas em Python, a biblioteca NetworkX oferece funções nx.eulerian_path e nx.hamiltonian_path para casos específicos, embora esta última seja apenas heurística e não garantia de solução. Há também pacotes especializados como OR-Tools da Google para problemas de roteamento com restrições reais que vão além do passeio puro. O site maintainido pela comunidade de teoria dos grafos computacional, disponível em interfaces como graphonline.ru e platforms similares, oferece visualizadores interativos úteis para experimentar com diferentes tipos de passeios e ver em tempo real como restrições de grau, conectividade e direcionalidade afetam a existencia de soluções. Para problemas de produção, recomendo começar com instancia pequena e validacao contra solucao conhecida antes de escalar, porque erros de implementacao em passeios sao frequentemente silenciosos — o algoritmo retorna algo que parece valido mas viola uma restricão secundaria que voce nao tinha considerado.
