Qual técnica algorítmica permite detectar ciclos em um grafo dirigido em tempo O(V+E)?
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Qual técnica algorítmica permite detectar ciclos em um grafo dirigido em tempo O(V+E)?
- A) Utiliza apenas marcação de estados brancos e pretos.
- B) Busca em profundidade (DFS) com marcação de estados (branco/cinza/preto) para identificar arestas de retorno.
- C) Busca em largura (BFS)
- D) Detecção de ciclo é O(E) apenas.
- E) Ciclo não pode ser detectado em grafos dirigidos.
✅ Resposta correta: alternativa B
Resolução passo a passo
- O problema pede a técnica que detecta ciclos em um grafo dirigido em tempo O(V+E), onde V é o número de vértices e E o número de arestas. Passo 2: A DFS (busca em profundidade) visita cada vértice e cada aresta uma vez, o que custa O(V+E). Passo 3: Durante a DFS, cada vértice recebe um estado: branco (não visitado), cinza (em visita, na pilha de recursão) ou preto (já finalizado). Passo 4: Existe ciclo se, ao examinar uma aresta de u para v, o vértice v está cinza, pois isso significa que v é ancestral de u na árvore de busca e a aresta é uma aresta de retorno. Passo 5: Por isso a alternativa B está correta e o gabarito oficial coincide com a resolução. Passo 6: A alternativa A está errada porque sem o estado cinza não é possível distinguir um vértice em processamento de um já finalizado, o que impede identificar arestas de retorno. Passo 7: A alternativa C está errada porque a BFS não usa a noção de ancestral na pilha de recursão e não identifica arestas de retorno de forma direta. Passo 8: A alternativa D está errada porque a complexidade O(E) ignora os vértices, e a detecção de ciclo custa O(V+E), não apenas O(E). Passo 9: A alternativa E está errada porque ciclos em grafos dirigidos são detectáveis, como em dependências circulares de tarefas, e isso é justamente o que a DFS faz.
💡 Dica: Considere as propriedades dos algoritmos de busca em profundidade.
Alternativa por alternativa
O aluno acredita que apenas duas cores bastam, sem perceber que o estado cinza é necessário para saber se um vértice ainda está no caminho atual da busca.
DFS visita vértices e arestas uma única vez; arestas que apontam para um vértice em estado 'cinza' indicam ciclo em grafo dirigido, resultando em O(V+E).
O aluno associa a detecção de ciclos a qualquer busca em grafos e supõe que a BFS, por visitar vértices por níveis, também identifica arestas de retorno.
Por que engana: Confundir a técnica de busca em largura com a busca em profundidade, acreditando que ambas têm a mesma eficiência na detecção de ciclos.
O aluno considera apenas o número de arestas no custo e esquece que o algoritmo também percorre todos os vértices, o que gera O(V+E).
O aluno transfere a intuição do dia a dia de que ciclos são coisas de grafos não dirigidos ou de caminhos fechados simples, e conclui que em grafos dirigidos eles não podem ser detectados.
Raio-X da questão
detecção de ciclos em grafos
avaliacao
grafos dirigidos · busca em profundidade
Revisar algoritmos de busca em profundidade e suas aplicações em grafos.
Confundir a técnica de busca em largura com a busca em profundidade, acreditando que ambas têm a mesma eficiência na detecção de ciclos.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Durante uma campanha de arrecadação, uma escola receberá alimentos e produtos de higiene para montar cestas destinadas a…
- Em um exercício de preparação para períodos de chuva intensa, uma central municipal de Defesa Civil precisa localizar…
- Em ações de fiscalização ambiental no Brasil, imagens de satélite podem ser comparadas em diferentes datas para indicar…
- Uma família criou um programa para organizar as compras do mês. O programa recebe os preços, soma os produtos e…
- — Sem conexão estável no rio, o alerta precisa aparecer no próprio tablet — afirmou a técnica que acompanha sons de aves…
- Falhas em formulários digitais de serviços públicos levaram um setor de tecnologia a testar cinco programas de análise…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog