- Escreva um algoritmo que recebe um caminho e verifica se ele é um ciclo
Passo 1
O enunciado pede um algoritmo que receba um caminho representado por uma sequência de vértices e determine se esse caminho forma um ciclo em um grafo. O conteúdo é teoria de grafos, mais especificamente a definição de ciclo simples, e vamos usar isso para estruturar nossa verificação.
Passo 2
Para que um caminho seja um ciclo simples, ele deve satisfazer três condições principais: (i) ter ao menos três arestas (ou seja, pelo menos quatro vértices na lista, já que o último repete o primeiro), (ii) o primeiro vértice coincidir com o último, e (iii) todos os vértices internos (exceto o primeiro/último) serem distintos. Vamos checar cada uma dessas condições em sequência.
Passo 3
Primeiro, vamos implementar as verificações básicas: calcular o tamanho da lista de vértices e confirmar se atende ao comprimento mínimo; comparar o primeiro e o último elemento da lista para garantir que fecham o ciclo.
Passo 4
Em seguida, para garantir a unicidade dos vértices internos, usamos um conjunto (set) para rastrear quais vértices já apareceram. Se algum vértice interno já tiver sido visto, concluímos que não é um ciclo simples. Se todas as checagens passarem, devolvemos verdadeiro; caso contrário, falso.
Resposta
função isCiclo(caminho):
// recebe uma lista de vértices [v₁, v₂, …, vₖ]
n ← comprimento(caminho)
// condição (i): pelo menos 3 arestas → n ≥ 4 vértices
se n < 4 então
retornar falso
// condição (ii): vértice inicial = vértice final
se caminho[0] ≠ caminho[n‒1] então
retornar falso
// condição (iii): vértices internos distintos
visitados ← conjunto vazio
para i de 0 até n‒2 faça
se caminho[i] ∈ visitados então
retornar falso
inserir caminho[i] em visitados
retornar verdadeiro
// recebe uma lista de vértices [v₁, v₂, …, vₖ]
n ← comprimento(caminho)
// condição (i): pelo menos 3 arestas → n ≥ 4 vértices
se n < 4 então
retornar falso
// condição (ii): vértice inicial = vértice final
se caminho[0] ≠ caminho[n‒1] então
retornar falso
// condição (iii): vértices internos distintos
visitados ← conjunto vazio
para i de 0 até n‒2 faça
se caminho[i] ∈ visitados então
retornar falso
inserir caminho[i] em visitados
retornar verdadeiro