Exercício 22.4-3 de CLRS3 ou CLRS2 - Dê um algoritmo que determine se um dado grafo não dirigido \mathrm{G}=(\mathrm{V}, \mathrm{E}) contém um ciclo simples. Esse algoritmo deve ser executado no tempo \mathrm{O}(\mathrm{V}), independentemente de |\mathrm{E}|.

Passo 1

O enunciado pede: dado um grafo não dirigido G=(V,E), decidir se G contém um ciclo simples. O algoritmo deve rodar em tempo \mathrm{O}(|V|), independentemente de |E|.\n
Informações dadas (resumo claro):
  • O grafo de entrada é G=(V,E) com n=|V| vértices e m=|E| arestas.
  • Queremos apenas responder “existe ciclo?” (sim/não).
  • A restrição de tempo é que o tempo total seja \mathrm{O}(n), sem depender de m.
    Observação: não estamos a pedir uma listagem de todos os ciclos, apenas a existência de pelo menos um ciclo simples.

Passo 2

Ideia-chave (observação combinatória simples que vai economizar tempo): um grafo sem ciclo é uma floresta (união de árvores). Numa árvore com k vértices o número de arestas é exatamente k-1. Para uma floresta com componentes cujos tamanhos em vértices são k_1,k_2,\dots,k_c temos que o número total de arestas satisfaz
m \le \sum_{i=1}^{c} (k_i-1) = \left(\sum_{i=1}^{c} k_i\right) - c = n - c,
onde c é o número de componentes conexas. Em particular m \le n-1 (pois c\ge 1).\n
Portanto, conclusão lógica útil: se
m \ge n
então o grafo não pode ser uma floresta e, portanto, necessariamente contém pelo menos um ciclo. Essa verificação usa apenas os valores n e m (que são parte natural da entrada).

Passo 3

Estratégia do algoritmo a partir da observação:
  1. Se m \ge n então responda “sim” (existe ciclo) imediatamente. Esse passo é \mathrm{O}(1).
  2. Caso contrário, temos m < n. Então o número de arestas é menor que o número de vértices, logo m = \mathrm{O}(n). Nesse caso podemos executar um algoritmo padrão de busca (DFS ou BFS) que detecta ciclos em tempo \mathrm{O}(n+m); como m < n isso dá \mathrm{O}(n) no pior caso — atendendo à restrição pedida.\n
    Resumo da razão: o caso difícil (muito grande) é resolvido pela observação combinatória sem examinar arestas; o caso restante tem poucas arestas e permite exploração direta.

Passo 4

Detalhe didático: como detectar um ciclo com DFS em grafo não dirigido (passo necessário quando m<n).
  • Estrutura de dados: vetor booleano \text{visitado}[u] para cada vértice u; e ao fazer DFS guardamos também o vértice pai \text{pai}[u] na árvore de busca.
  • Rotina DFS-visit(u):
    • marque \text{visitado}[u]=\text{true}.
    • para cada vizinho v de u:
      • se \text{visitado}[v]=\text{false}: coloque \text{pai}[v]=u e chame DFS-visit( v).
      • senão (ou seja, \text{visitado}[v]=\text{true}) e v\neq \text{pai}[u]: então encontramos uma aresta que liga u a um vértice já visitado que não é seu pai na árvore de busca — isso prova a existência de um ciclo simples; podemos parar e responder “sim”.
  • Explicação por que isso detecta um ciclo: em grafo não dirigido, toda aresta usada na árvore de busca tem seu outro extremo como pai/filho; se vemos uma aresta para um vértice já visitado que não é o pai, então existe um caminho simples entre v e u na árvore de busca mais a aresta (u,v), formando um ciclo simples.
  • Observação prática: ao usar lista de adjacência, cada aresta aparece duas vezes (uma em cada lista), mas a análise de tempo padrão dá \mathrm{O}(n+m).

Passo 5

Pseudocódigo final (em palavras e passos claros):
  1. Recebe G=(V,E), com n=|V| e m=|E|.
  2. Se m \ge n então retorne “sim” (existe ciclo) e termine.
  3. Senão (isto é, m < n):
    • Inicialize \text{visitado}[u]=\text{false} e \text{pai}[u]=\text{null} para todo u\in V.
    • Para cada u\in V: se \text{visitado}[u]=\text{false} faça DFS-visit( u) seguindo o procedimento do Passo 4; se algum DFS-visit detectar ciclo, retorne “sim”.
    • Se terminar todas as componentes sem detectar ciclo, retorne “não”.
      Comentários sobre implementação: assuma que a entrada fornece também o valor m (número total de arestas). Se o modelo de entrada não der m explicitamente, pode-se passar pela lista de arestas uma vez para contar m (isso custaria \mathrm{O}(m), o que violaria a restrição se m for grande) — por isso a formulação do exercício normalmente permite acessar o valor m sem varrer todas as arestas.

Passo 6

Prova de corretude (resumida):
  • Se m\ge n a observação do Passo 2 prova que o grafo não pode ser acíclico; então existe ciclo — correção imediata.
  • Se m<n: o algoritmo de DFS é conhecido por detectar ciclos em grafos não dirigidos: encontrar um vizinho já visitado que não seja o pai implica existência de ciclo; se não encontrarmos tal situação então o grafo é uma floresta (acyclic) e o algoritmo corretamente retorna “não”. Portanto o algoritmo está correto em ambos os casos.

Passo 7

Análise de complexidade detalhada:
  • Verificação inicial m \ge n custa \mathrm{O}(1).
  • No caso m<n, o custo do DFS é \mathrm{O}(n+m). Como m<n temos n+m < 2n, portanto o custo é \mathrm{O}(n).
  • Logo, o tempo total do algoritmo é \mathrm{O}(n) no pior caso, independente de m (pois quando m é grande o algoritmo nem examina as arestas; quando m é pequeno o DFS é linear em n).\n
    Complexidade espacial padrão adicional é \mathrm{O}(n) por conta dos vetores \text{visitado} e \text{pai}.

Resposta

Se |E| \ge |V| então responda “sim” (existe ciclo). Caso contrário (isto é, |E|<|V|) execute uma busca em profundidade (DFS) que detecta aresta para vértice já visitado diferente do pai; se a DFS encontrar tal aresta responda “sim”, senão responda “não”. Este algoritmo roda em \mathrm{O}(|V|).

Exercícios relacionados