Em um algoritmo de busca em largura (BFS) aplicado a um grafo, qual é a função da variável booleana 'visitado'…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um algoritmo de busca em largura (BFS) aplicado a um grafo, qual é a função da variável booleana 'visitado' associada a cada nó?
- A) Usar a variável 'visitado' para determinar a ordem de processamento dos nós.
- B) Indicar quais nós já foram explorados para evitar visitas repetidas e prevenir ciclos.
- C) Marcar nós como visitados para garantir que o BFS não encontre nós com valor nulo.
- D) 'Visitado' impede que o algoritmo inicie a busca em nós já explorados.
- E) A variável 'visitado' é usada para armazenar o valor dos nós durante a busca.
✅ Resposta correta: alternativa B
Resolução passo a passo
- O BFS percorre o grafo por níveis, a partir de um nó inicial, usando uma fila. Como um grafo pode ter ciclos (ou simplesmente nós alcançáveis por vários caminhos), é preciso registrar quais nós já foram explorados. Esse é o papel da variável booleana 'visitado', associada a cada nó. Passo 2: Ao descobrir um vizinho, o algoritmo consulta 'visitado'. Se for falso, marca como verdadeiro, enfileira o nó e o trata. Se já for verdadeiro, ignora o nó. Assim cada nó é processado uma única vez e os ciclos não geram laços infinitos. Passo 3: Por isso a alternativa B é a correta, pois afirma exatamente que a variável indica os nós já explorados, evitando visitas repetidas e prevenindo ciclos. Passo 4: A alternativa A está errada, porque a ordem de processamento em BFS é definida pela fila (FIFO), e não pela variável 'visitado'. Passo 5: A alternativa C está errada, pois 'visitado' não tem relação com valores nulos; sua função é controlar repetição de visitas. Passo 6: A alternativa D está errada na formulação: 'visitado' não impede o início da busca, e sim a inclusão ou o processamento de nós já explorados durante a busca, que é o que a alternativa B descreve com precisão. Passo 7: A alternativa E está errada, porque a variável é booleana e indica apenas se o nó foi explorado; ela não armazena o valor do nó, que é outra informação do grafo.
💡 Dica: Considere o papel da variável 'visitado' na prevenção de ciclos.
Alternativa por alternativa
O aluno acredita que a marcação 'visitado' decide a ordem em que os nós são processados, confundindo o controle de repetição com a estratégia de escolha do próximo nó.
Por que engana: Confundir a função da variável 'visitado' com a ordem de processamento dos nós, acreditando que ela determina a sequência de exploração.
Marcar vértices como visitados impede enfileirar e processar o mesmo nó várias vezes, garantindo correção e eficiência do BFS (cada aresta é examinada no máximo uma vez).
O aluno associa 'visitado' a valores nulos, imaginando que a marcação serve para verificar nós vazios ou inválidos, e não para controlar repetição de visitas.
O aluno entende que 'visitado' bloqueia o início da busca em certos nós, quando na prática a verificação ocorre ao descobrir ou enfileirar vizinhos, e a alternativa é imprecisa ao descrever esse momento.
O aluno confunde a variável booleana de controle com a estrutura que guarda dados, imaginando que 'visitado' armazena o valor do nó durante a busca.
Raio-X da questão
busca em largura
avaliacao
estruturas de dados · algoritmos de busca
Revisar o funcionamento do algoritmo BFS e a utilização de variáveis booleanas.
Confundir a função da variável 'visitado' com a ordem de processamento dos nós, acreditando que ela determina a sequência de exploração.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em um algoritmo de busca em grafos que utiliza uma variável booleana 'visitado' para cada vértice, qual é a função dessa…
- Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…
- Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…
- Em uma implementação de busca em largura (BFS) em grafos, qual estrutura de dados é essencial para manter a ordem de…
- Descreva, em termos de algoritmo que usa a variável 'visitado', como contar o número de componentes conexos em uma rede…
- Explique como um algoritmo baseado em DFS (busca em profundidade) identifica a presença de ciclo em um grafo dirigido…
Todas as questões de Organização e representação da informação
🔎 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