Busca em largura (BFS)

Text Material Preview

Busca em largura (BFS) 
O que caracteriza a busca em largura (BFS) em um grafo?
a) A busca realiza uma exploracao profunda dos nos antes de expandir os vizinhos.
b) A busca explora todos os nos ao longo de um caminho ate encontrar o destino.
c) A busca expande todos os vizinhos de um no antes de avancar para os nos mais distantes.
d) A busca segue um caminho aleatorio ate encontrar o no desejado.
Resposta correta: c) A busca expande todos os vizinhos de um no antes de avancar para os nos
mais distantes.
Explicacao: A busca em largura explora os nos camada por camada, visitando todos os nos de
distancia 1, depois todos os de distancia 2, e assim por diante.
Qual e a estrutura de dados fundamental utilizada para a implementacao da BFS?
a) Pilha (Stack)
b) Fila (Queue)
c) Lista (List)
d) Arvore (Tree)
Resposta correta: b) Fila (Queue)
Explicacao: A BFS utiliza uma fila para gerenciar a ordem de exploracao dos nos. Os nos sao
visitados em ordem de chegada.
Quando um algoritmo de BFS e mais vantajoso para ser utilizado?
a) Quando e necessario encontrar o caminho mais curto em um grafo nao ponderado.
b) Quando e necessario percorrer todos os nos do grafo sem preocupacao com o caminho mais
curto.
c) Quando o grafo e muito denso.
d) Quando se deseja evitar a visita a nos repetidos.
Resposta correta: a) Quando e necessario encontrar o caminho mais curto em um grafo nao
ponderado.
Explicacao: A BFS e ideal para encontrar o caminho mais curto em grafos nao ponderados, pois
explora os nos nivel a nivel.
Como a BFS lida com ciclos no grafo?
a) Ignora os ciclos e continua a busca normalmente.
b) Enfrenta um ciclo sem problemas, pois a busca nunca ira revisitar nos.
c) Evita visitar nos ja explorados para nao entrar em ciclos infinitos.
d) Apenas interrompe a busca quando um ciclo e encontrado.
Resposta correta: c) Evita visitar nos ja explorados para nao entrar em ciclos infinitos.
Explicacao: A BFS marca os nos visitados para evitar que o algoritmo entre em ciclos e fique preso
em um laco infinito.
Em qual situacao a BFS pode nao ser a melhor escolha para um problema?
a) Quando o grafo e ponderado e precisamos do caminho mais curto.
b) Quando o grafo nao contem ciclos.
c) Quando e necessario buscar informacoes sobre todos os nos do grafo.
d) Quando o grafo e muito grande e nao contem solucoes.
Resposta correta: a) Quando o grafo e ponderado e precisamos do caminho mais curto.
Explicacao: A BFS nao e a melhor escolha em grafos ponderados, pois ela nao leva em
consideracao os pesos das arestas, o que pode levar a solucoes subotimas.
Qual e a principal vantagem da BFS sobre a DFS (Busca em Profundidade)?
a) A BFS pode encontrar solucoes mais rapidamente em grafos grandes.
b) A BFS encontra a solucao mais rapidamente em grafos com muitos ciclos.
c) A BFS encontra o caminho mais curto em grafos nao ponderados.
d) A BFS e menos propensa a consumir muita memoria.
Resposta correta: c) A BFS encontra o caminho mais curto em grafos nao ponderados.
Explicacao: A BFS e otima para encontrar o caminho mais curto em grafos nao ponderados, porque
explora os nos de forma equilibrada e camada por camada.
Ao executar BFS em um grafo, o que acontece quando a fila de nos a ser explorados esta vazia?
a) O algoritmo continua a busca sem parar.
b) O algoritmo retorna uma solucao incompleta.
c) O algoritmo encerra a execucao, indicando que todos os nos foram explorados.
d) O algoritmo gera um erro e termina a execucao.
Resposta correta: c) O algoritmo encerra a execucao, indicando que todos os nos foram
explorados.
Explicacao: Quando a fila esta vazia, isso significa que todos os nos acessiveis foram explorados e
nao ha mais nos para visitar.
Qual das alternativas e uma aplicacao tipica do algoritmo de BFS?
a) Encontrar o caminho mais curto em um mapa sem considerar distancias.
b) Realizar a busca em profundidade de todos os nos de um grafo.
c) Verificar se um grafo e conexo.
d) Encontrar o ciclo mais curto em um grafo ponderado.
Resposta correta: a) Encontrar o caminho mais curto em um mapa sem considerar distancias.
Explicacao: A BFS e amplamente utilizada para encontrar o caminho mais curto em grafos nao
ponderados, como um mapa onde cada aresta tem o mesmo peso.
O que ocorre se um grafo contiver uma aresta de peso negativo e o algoritmo de BFS for
executado?
a) O algoritmo pode produzir um caminho incorreto, pois nao leva em conta os pesos negativos.
b) A BFS pode nao funcionar corretamente, retornando erros ao lidar com arestas negativas.
c) O algoritmo ignora as arestas de peso negativo e segue normalmente.
d) A BFS ainda retorna o caminho mais curto, mas com desempenho inferior.
Resposta correta: a) O algoritmo pode produzir um caminho incorreto, pois nao leva em conta os
pesos negativos.
Explicacao: A BFS nao funciona corretamente com arestas de peso negativo, pois ela nao
considera os pesos ao explorar os nos.
Em um grafo com varias componentes desconexas, o que a BFS ira retornar ao ser executada em
um no inicial?
a) Ela retornara o caminho para todos os nos do grafo, independentemente de serem alcancaveis.
b) Ela explorara todos os nos dentro da componente conectada ao no inicial.
c) Ela retornara um erro se houver componentes desconexas.
d) Ela encontrara um caminho para todas as componentes desconexas do grafo.
Resposta correta: b) Ela explorara todos os nos dentro da componente conectada ao no inicial.
Explicacao: A BFS so explora a componente do grafo conectada ao no inicial. Para explorar o
restante do grafo, seria necessario iniciar uma nova busca a partir de outro no de uma componente
desconexa.
Quais dos seguintes problemas a BFS pode resolver eficientemente?
a) Encontrar o caminho mais curto entre dois pontos em um grafo nao ponderado.
b) Calcular o maior ciclo de um grafo ponderado.
c) Encontrar todos os nos em um grafo ponderado que estao a uma distancia k de um no inicial.
d) Encontrar o maior caminho de um grafo sem ciclos.
Resposta correta: a) Encontrar o caminho mais curto entre dois pontos em um grafo nao
ponderado.
Explicacao: A BFS e eficiente para encontrar o caminho mais curto em grafos nao ponderados, pois
explora os nos camada por camada.
Ao executar BFS, qual seria a estrutura de dados usada para armazenar os nos ainda nao
visitados?
a) Pilha (Stack)
b) Fila (Queue)
c) Conjunto (Set)
d) Arvore (Tree)
Resposta correta: b) Fila (Queue)
Explicacao: A BFS utiliza uma fila para armazenar os nos ainda nao visitados, garantindo que os
nos mais proximos sejam visitados primeiro.
O que acontece se a BFS for executada em um grafo com uma estrutura de arvore?
a) A BFS nao funcionara, pois nao e possivel percorrer arvores.
b) A BFS encontrara o caminho mais curto em um numero de passos proporcional a altura da
arvore.
c) A BFS encontrara o caminho mais curto, mas de forma ineficiente, em relacao a profundidade da
arvore.
d) A BFS nao tera um desempenho notavel, pois ja existe uma ordem natural de visitacao.
Resposta correta: b) A BFS encontrara o caminho mais curto em um numero de passos
proporcional a altura da arvore.
Explicacao: Em uma arvore, a BFS pode ser usada para encontrar o caminho mais curto entre dois
nos, com a eficiencia dependendo da altura da arvore.
Quais sao as principais desvantagens do algoritmo de BFS?
a) Ele consome muita memoria, pois precisa armazenar todos os nos na fila.
b) Ele nao consegue lidar com grafos grandes e complexos.
c) Ele nao encontra o caminho mais curto em grafos ponderados.
d) Ele nunca termina em grafos grandes.
Resposta correta: a) Ele consome muita memoria, pois precisa armazenar todos os nos na fila.
Explicacao: A principal desvantagem da BFS e o consumo de memoria, ja que ela precisa
armazenar todos os nos que ainda precisam ser visitados.
15