Em um algoritmo de busca em grafos que utiliza uma variável booleana 'visitado' para cada vértice, qual é a…

Questão

Em um algoritmo de busca em grafos que utiliza uma variável booleana 'visitado' para cada vértice, qual é a função dessa variável?

1. A) Indicar se o vértice é o ponto de partida da busca.
2. B) Armazenar o custo de explorar um vértice.
3. C) Marcar os vértices que formam ciclos no grafo.
4. D) Contar o número de arestas ligadas ao vértice.
5. E) Marcar se o vértice já foi explorado para evitar visitas repetidas.

✅ Resposta correta: alternativa E

Resolução passo a passo

1. Em algoritmos de busca em grafos, como busca em largura (BFS) e busca em profundidade (DFS), é necessário controlar quais vértices já foram alcançados, pois grafos podem conter ciclos e vértices ligados por múltiplos caminhos.
2. A variável booleana 'visitado' funciona como uma marcação: começa como falso para todos os vértices e passa a verdadeiro quando o vértice é explorado pela primeira vez.
3. Antes de processar um vizinho, o algoritmo consulta essa marcação. Se ele já estiver marcado como visitado, é ignorado, o que impede laços infinitos e visitas repetidas.
4. Analisando as alternativas: A está errada, pois o ponto de partida é definido pelo próprio algoritmo e não é a função da variável. B está errada, pois o custo de exploração não é representado por essa variável booleana. C está errada, pois a variável não identifica ciclos; ela apenas registra se o vértice já foi alcançado. D está errada, pois o número de arestas é obtido pelo grau do vértice, não por essa variável. E está correta, pois descreve exatamente a função de controle de visitas repetidas.
5. Conclusão: a alternativa correta é a E, coincidindo com o gabarito oficial.

💡 Dica: Considere como o registro de vértices já visitados controla a busca no grafo.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Em um algoritmo de busca em largura (BFS) aplicado a um grafo, qual é a função da variável booleana 'visitado' associada…
• Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…
• Descreva, em termos de algoritmo que usa a variável 'visitado', como contar o número de componentes conexos em uma rede…
• Em um algoritmo que identifica componentes conexas em um grafo não direcionado usando DFS, qual variável (tipo de dado)…
• Explique como um algoritmo baseado em DFS (busca em profundidade) identifica a presença de ciclo em um grafo dirigido…
• Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…

Todas as questões de [CONFERIR] Construir soluções baseadas no uso de algoritmos e conceitos da Computação para resolver problemas, avaliando suas qualidades e melhorando-as.