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
- Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências…
- Explique como um algoritmo baseado em DFS (busca em profundidade) identifica a presença de ciclo em um grafo dirigido…
- Projete um algoritmo em pseudocódigo para detectar ciclos em um grafo dirigido representado por listas de adjacência…
- Descreva um algoritmo, indicando as variáveis-chave e os passos, para detectar ciclos em um grafo dirigido usando…
- A tabela de arestas (dados) de um grafo dirigido é: 1?2, 2?3, 3?1, 3?4. Usando um algoritmo de detecção, analise se…
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
🔎 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