Algoritmo de Hierholzer
Santos, P. H. P.1 Bandeira, L. F. P.2
1 Centro de Desenvolvimento Tecnológico
Universidade Federal de Pelotas
2 Centro de Desenvolvimento Tecnológico
Universidade Federal de Pelotas
Algoritmos e Estruturas de Dados II, Março de 2025
Sumário
1 Introdução
2 Exemplos
3 Pseudocódigo
4 Aplicações
2/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Sumário
1 Introdução
2 Exemplos
3 Pseudocódigo
4 Aplicações
3/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Do que o algoritmo é capaz?
• Grafo não direcionado
• Caminho euleriano
• Ciclo euleriano
• Grafo direcionado
• Caminho euleriano
• Ciclo euleriano
4/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho Euleriano
O que é um Caminho Euleriano?
Definição
Um caminho euleriano (ou trilha euleriana) é um caminho em um grafo não direcionado que
visita cada aresta exatamente uma vez.
5/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Circuito Euleriano
O que é um Circuito Euleriano?
Definição
Um Circuito euleriano é um caminho euleriano em particular que inicia e termina no mesmo
vértice
6/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Condições para Caminho e Circuito Euleriano
Tipo de Grafo Circuito Euleriano Caminho Euleriano
Ou todos os vértices têm grau par
Não Direcionado Todo vértice possui grau par ou exatamente dois vértices
têm grau ímpar
No máximo um vértice tem
(grau de saída) − (grau de entrada) = 1,
Todo vértice tem grau de entrada no máximo um vértice tem
Direcionado
igual ao grau de saída (grau de entrada) − (grau de saída) = 1,
e todos os demais vértices têm
grau de entrada igual ao grau de saída
7/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Encontrando um caminho euleriano em um grafo direcionado
Passo 1: Verificar a existência do caminho
Condições Necessárias
• Diferença de graus:
• No máximo um vértice tem outdegree − indegree = 1 (início do caminho)
• No máximo um vértice tem indegree − outdegree = 1 (fim do caminho)
• Todos os demais vértices têm indegree = outdegree
*Se todas as diferenças de grau forem zero, o caminho é um circuito euleriano.
8/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Encontrando um caminho euleriano em um grafo direcionado
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
9/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Condições para um caminho euleriano
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
• Nó 1: Grau de entrada - Grau de saída = 1
• Nó 6: Grau de saída - Grau de entrada = 1
10/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Fazendo a busca de profundidade em um grafo euleriano
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
11/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Fazendo a busca de profundidade em um grafo euleriano
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
12/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Fazendo a busca de profundidade em um grafo euleriano
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
13/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Fazendo a busca de profundidade em um grafo euleriano
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
14/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Fazendo a busca de profundidade em um grafo euleriano
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
15/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Fazendo a busca de profundidade em um grafo euleriano
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
16/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Fazendo a busca de profundidade em um grafo euleriano
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
17/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Fazendo a busca de profundidade em um grafo euleriano
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
18/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Fazendo a busca de profundidade em um grafo euleriano
Nó Entrada Saída
0 0 0
1 1 2 2 4 6
2 3 3
3 3 3 0
4 2 2
5 1 1
6 2 1 1 3 5
19/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Sumário
1 Introdução
2 Exemplos
3 Pseudocódigo
4 Aplicações
20/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
21/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
22/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
23/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
24/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
25/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
Solução: [4]
26/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
Solução: [3, 4]
27/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
Solução: [3, 4]
28/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
Solução: [3, 4]
29/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
Solução: [1, 3, 4]
30/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
Solução: [2, 1, 3, 4]
31/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
Solução: [1, 2, 1, 3, 4]
32/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
0 1 3 4
Solução: [0, 1, 2, 1, 3, 4]
33/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 2
2 3
3 3 0
4 2
5 1
6 1
1 3 5
34/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 2
2 3
3 3 0
4 2
5 1
6 1
1 3 5
35/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 1
2 3
3 3 0
4 2
5 1
6 1
1 3 5
36/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 1
2 3
3 2 0
4 2
5 1
6 1
1 3 5
37/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 1
2 3
3 2 0
4 2
5 0
6 1
1 3 5
38/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 1
2 3
3 2 0
4 2
5 0
6 0
1 3 5
39/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 1
2 3
3 1 0
4 2
5 0
6 0
1 3 5
40/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 1
2 2
3 1 0
4 2
5 0
6 0
1 3 5
41/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 1
2 2
3 1 0
4 1
5 0
6 0
1 3 5
42/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 1
2 2
3 1 0
4 1
5 0
6 0
1 3 5
Solução: [6]
43/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 1
2 2
3 1 0
4 0
5 0
6 0
1 3 5
Solução: [6]
44/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 1
2 2
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [6]
45/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 2
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [6]
46/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 1
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [6]
47/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 1
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [4, 6]
48/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [4, 6]
49/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [2, 4, 6]
50/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [2, 2, 4, 6]
51/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [1, 2, 2, 4, 6]
52/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [3, 1, 2, 2, 4, 6]
53/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [4, 3, 1, 2, 2, 4, 6]
54/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [2, 4, 3, 1, 2, 2, 4, 6]
55/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [3, 2, 4, 3, 1, 2, 2, 4, 6]
56/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
57/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
58/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
59/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
Nó Grau
0 0 2 4 6
1 0
2 0
3 0 0
4 0
5 0
6 0
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
60/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
61/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
62/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
63/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
64/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
65/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
66/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
67/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
68/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
69/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
70/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
71/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
72/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
73/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
74/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Caminho euleriano em um grafo direcionado
2 4 6
1 3 5
Solução: [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
75/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Sumário
1 Introdução
2 Exemplos
3 Pseudocódigo
4 Aplicações
76/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Algoritmo de Hierholzer para Caminho Euleriano
1 # Variáveis globais/escopo de classe
2 n = número de vértices no grafo
3 m = número de arestas no grafo
4 g = lista de adjacência representando um grafo direcionado
5
6 in = [0, 0, …, 0, 0] # Tamanho n
7 out = [0, 0, …, 0, 0] # Tamanho n
8
9 caminho = lista encadeada vazia
10
11 function encontrarCaminhoEuleriano():
12 contarGrausEntradaSaida()
13 if not grafoPossuiCaminhoEuleriano(): return null
14
15 dfs(encontrarNoInicial())
16 if [Link]() == m+1: return caminho
17 return null
77/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Sumário
1 Introdução
2 Exemplos
3 Pseudocódigo
4 Aplicações
78/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Aplicações
• Automação de design eletrônico (EDA)
• Bioinformática
• Logística e transporte
• Robótica e automatização industrial
• Roteamento de redes
79/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Rede Static CMOS - NAND
Vdd
Vdd
A B B A
OUT OUT
OUT
A
n1 B A
B
n1 OUT
80/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Fim
Obrigado!
81/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer
Referências
[1] William Fiset.
Eulerian path/circuit algorithm (hierholzer’s algorithm) | graph theory.
[Link] 2018.
Acessado: 05 de Março de 2025.
[2] Steven Halim, Felix Halim, and Suhendry Effendy.
Competitive Programming 4-Book 2: The Lower Bound of Programming Contests in the 2020s.
Lulu, 2020.
82/82 Pedro Santos, Luiz Bandeira Algoritmo de Hierholzer