*51. Expresse o algoritmo de Fleury em pseudocódigo.
Passo 1
O enunciado pede para escrever em pseudocódigo o algoritmo de Fleury, que constrói um caminho ou circuito euleriano em um grafo conexo. Para isso precisamos dos conceitos de grafo Euleriano (grau par em todos os vértices, ou exatamente dois de grau ímpar), detecção de ponte (aresta cuja remoção aumenta o número de componentes) e operações básicas em grafos (grau, listas de adjacência, remoção de aresta).
Passo 2
Primeiro verificamos se o grafo
tem caminho ou circuito euleriano:
- Se não tiver 0 ou 2 vértices de grau ímpar, o algoritmo não é aplicável.
- Se tiver 0 vértices de grau ímpar, vamos gerar um circuito; se tiver 2, geramos um trilha começando em um dos vértices de grau ímpar.
Em seguida inicializamos:
-vértice inicial
-lista vazia para acumular arestas na ordem visitada
Passo 3
Agora entramos no laço principal:
Enquanto houver arestas incidentes em :
Enquanto houver arestas incidentes em
- Examine cada aresta
em . - Escolha a primeira que não seja ponte, a menos que seja a única aresta restante em
. - Adicione
ao fim de . - Remova
de . - Atualize
.
Passo 4
Quando não restarem arestas incidentes em
, o laço termina e
contém o caminho (ou circuito) euleriano de
.
Resposta
Algoritmo Fleury
se número de vértices de grau ímpar e
então
retornar “não é Euleriano”
fim se
se existem 2 vértices de grau ímpar
então um vértice de grau ímpar
senão
qualquer vértice de grau não-nulo
fim se
lista vazia
enquanto grau > 0 faça
para cada aresta em
faça
se não é ponte em
ou é a única aresta incidente em
então
escolha e interrompa o laço interno
fim se
fim para
remover de
fim enquanto
retornar
se número de vértices de grau ímpar
então
retornar “não é Euleriano”
fim se
se existem 2 vértices de grau ímpar
então
senão
fim se
enquanto grau
para cada aresta
se
escolha
fim se
fim para
remover
fim enquanto
retornar