Busca em largura (BFS)

Vista previa del material en texto

Busca em largura (BFS) 
Qual e a principal caracteristica do algoritmo de busca em largura (BFS)?
a) Visita os vertices em profundidade antes de visitar os vizinhos.
b) Visita os vertices nivel por nivel, comecando pelo vertice inicial.
c) Sempre encontra o caminho mais longo entre dois vertices.
d) Funciona apenas em grafos nao direcionados.
Resposta: b) Visita os vertices nivel por nivel, comecando pelo vertice inicial.
Explicacao: O BFS explora todos os vertices de um nivel antes de passar para o proximo,
garantindo que os nos mais proximos do ponto de partida sejam visitados primeiro.
Qual estrutura de dados e fundamental para a implementacao do BFS?
a) Pilha
b) Fila
c) Lista ligada
d) Arvore binaria
Resposta: b) Fila
Explicacao: O BFS usa uma fila para armazenar os vertices a serem visitados na ordem correta,
garantindo que os vertices sejam processados nivel por nivel.
Em um grafo nao ponderado, qual e uma propriedade importante do BFS?
a) Sempre encontra o caminho mais curto em termos de numero de arestas entre dois vertices.
b) Pode encontrar caminhos mais longos antes dos curtos.
c) Funciona apenas em grafos direcionados.
d) Sempre visita os vertices em ordem alfabetica.
Resposta: a) Sempre encontra o caminho mais curto em termos de numero de arestas entre dois
vertices.
Explicacao: Como o BFS explora todos os vizinhos de um vertice antes de avancar para o proximo
nivel, ele garante que o primeiro caminho encontrado para um vertice seja o de menor numero de
arestas.
Qual e a complexidade de tempo do BFS em um grafo representado por lista de adjacencia?
a) O(n2)
b) O(n + m), onde n e o numero de vertices e m o numero de arestas
c) O(log n)
d) O(n!)
Resposta: b) O(n + m), onde n e o numero de vertices e m o numero de arestas
Explicacao: Cada vertice e visitado uma vez, e cada aresta e examinada no maximo duas vezes em
grafos nao direcionados, resultando em complexidade O(n + m).
Qual e a complexidade de espaco do BFS em um grafo com n vertices?
a) O(1)
b) O(n)
c) O(n2)
d) O(log n)
Resposta: b) O(n)
Explicacao: O BFS mantem uma fila que pode conter todos os vertices de um nivel, alem de
estruturas auxiliares para marcar vertices visitados, exigindo espaco proporcional ao numero de
vertices.
Em um grafo ponderado, o BFS sozinho:
a) Sempre encontra o caminho de menor custo.
b) Nao garante o menor custo, apenas o menor numero de arestas.
c) Nao pode ser executado.
d) Funciona apenas se os pesos forem inteiros positivos.
Resposta: b) Nao garante o menor custo, apenas o menor numero de arestas.
Explicacao: O BFS considera apenas a distancia em numero de arestas e nao leva em conta
pesos. Para encontrar o caminho de menor custo em grafos ponderados, e necessario usar o
algoritmo de Dijkstra ou Bellman-Ford.
Qual e a principal diferenca entre BFS e DFS (busca em profundidade)?
a) BFS visita vertices de forma aleatoria, enquanto DFS visita nivel por nivel.
b) BFS usa fila e DFS usa pilha ou recursao.
c) BFS funciona apenas em grafos direcionados, DFS apenas em nao direcionados.
d) BFS sempre encontra caminhos mais longos que DFS.
Resposta: b) BFS usa fila e DFS usa pilha ou recursao.
Explicacao: O BFS explora todos os vizinhos de um vertice antes de avancar, utilizando fila,
enquanto o DFS explora um caminho ate o fim antes de retroceder, utilizando pilha ou chamadas
recursivas.
Em que situacao o BFS e particularmente util?
a) Quando se quer detectar ciclos rapidamente em um grafo ponderado.
b) Quando se deseja encontrar o caminho mais curto em grafos nao ponderados.
c) Para ordenar topologicamente um grafo.
d) Para encontrar o menor peso de arestas em grafos ponderados.
Resposta: b) Quando se deseja encontrar o caminho mais curto em grafos nao ponderados.
Explicacao: Devido a sua exploracao nivel por nivel, o BFS e ideal para encontrar o caminho com o
menor numero de arestas entre dois vertices em grafos nao ponderados.
Ao executar BFS, como podemos rastrear o caminho entre o vertice inicial e um vertice alvo?
a) Armazenando apenas os vertices visitados.
b) Mantendo um array de predecessores que indica o vertice anterior de cada vertice visitado.
c) Utilizando apenas a fila para processar vertices.
d) Nao e possivel rastrear caminhos com BFS.
Resposta: b) Mantendo um array de predecessores que indica o vertice anterior de cada vertice
visitado.
Explicacao: Guardando o predecessor de cada vertice, podemos reconstruir o caminho minimo do
vertice inicial ate qualquer vertice atingivel pelo BFS.
Qual e o comportamento do BFS em grafos desconectados?
a) Ele encontra todos os vertices automaticamente.
b) Ele visita apenas o componente conectado ao vertice inicial.
c) Ele falha ao encontrar vertices em outros componentes.
d) Ele ignora os vertices ja visitados.
Resposta: b) Ele visita apenas o componente conectado ao vertice inicial.
Explicacao: O BFS so explora vertices que sao acessiveis a partir do ponto de partida. Para visitar
todos os vertices de um grafo desconectado, e necessario iniciar BFS a partir de cada componente
nao visitado.
Qual e a utilidade de marcar os vertices como visitados no BFS?
a) Garantir que o algoritmo percorra cada vertice apenas uma vez e evite loops infinitos.
b) Aumentar o numero de comparacoes.
c) Reduzir a complexidade de espaco para O(1).
d) Permitir que o algoritmo funcione apenas em grafos direcionados.
Resposta: a) Garantir que o algoritmo percorra cada vertice apenas uma vez e evite loops infinitos.
Explicacao: Marcar vertices visitados evita revisitar nos, prevenindo ciclos infinitos em grafos
ciclicos.
Qual e a ordem tipica de execucao do BFS em um grafo representado por matriz de adjacencia?
a) O(n3)
b) O(n2)
c) O(n log n)
d) O(n)
Resposta: b) O(n2)
Explicacao: Cada verificacao de vizinhos em uma matriz de adjacencia requer percorrer todas as
entradas da linha correspondente, resultando em complexidade O(n2).
Em BFS, o que determina a ordem em que os vizinhos de um vertice sao visitados?
a) Sempre na ordem crescente dos indices dos vertices.
b) A ordem depende da estrutura de dados usada para armazenar os vizinhos, geralmente uma
lista de adjacencia.
c) Ordem aleatoria.
d) Ordem decrescente do peso das arestas.
Resposta: b) A ordem depende da estrutura de dados usada para armazenar os vizinhos,
geralmente uma lista de adjacencia.
Explicacao: A BFS visita os vizinhos na ordem em que eles aparecem na lista de adjacencia ou fila
de adjacencia.
Qual e a principal limitacao do BFS?
a) Nao consegue encontrar caminhos curtos em grafos nao ponderados.
b) Pode consumir muita memoria se o grafo tiver muitos vertices ou niveis amplos.
c) Nao funciona em grafos direcionados.
d) Sempre visita vertices fora de ordem.
Resposta: b) Pode consumir muita memoria se o grafo tiver muitos vertices ou niveis amplos.
Explicacao: Como BFS mantem todos os vertices de um nivel na fila, grafos muito largos podem
exigir grandes quantidades de memoria.
Qual e a diferenca entre BFS e busca em largura limitada (BFS limitada a um nivel)?
a) BFS limitada visita apenas vertices em niveis proximos ao inicial, ignorando niveis mais
distantes.
b) BFS limitada nao usa fila.
c) BFS limitada encontra sempre caminhos mais longos.
d) Nao ha diferenca; sao equivalentes.
Resposta: a) BFS limitada visita apenas vertices em niveis proximos ao inicial, ignorando niveis
mais distantes.
Explicacao: Em problemas como redes sociais ou jogos, as vezes so e necessario explorar ate uma
profundidade maxima, evitando explorar todos os niveis do grafo.
Como o BFS pode ser utilizado para detectar ciclos em um grafo nao direcionado?
a) Comparando pesos das arestas.
b) Se um vertice vizinho ja visitado nao for o pai do vertice atual, ha um ciclo.
c) BFS nao consegue detectar ciclos.
d) Contando o numero de vertices.
Resposta: b) Se um vertice vizinho ja visitado nao for o pai do vertice atual, ha um ciclo.
Explicacao: Ao visitar cada vertice, se encontrarmos um vizinho ja visitadoque nao seja o vertice
que nos levou ate o atual, isso indica a presenca de um ciclo.
Qual e a vantagem de usar BFS em vez de DFS para encontrar caminhos mais curtos em grafos
nao ponderados?
a) DFS usa menos memoria.
b) BFS garante encontrar o caminho de menor numero de arestas.
c) DFS e mais rapido.
d) BFS funciona apenas em grafos direcionados.
Resposta: b) BFS garante encontrar o caminho de menor numero de arestas.
Explicacao: DFS pode encontrar caminhos arbitrarios, que nao sao necessariamente os mais
curtos, enquanto BFS garante o caminho minimo em numero de arestas.
Em grafos ponderados com pesos iguais, BFS pode ser usado para:
a) Encontrar o caminho de menor custo.
b) Encontrar o caminho mais longo.
c) Ordenar os vertices.
d) Determinar o grau dos vertices.
Resposta: a) Encontrar o caminho de menor custo.
Explicacao: Quando todas as arestas tem o mesmo peso, o menor numero de arestas equivale ao
menor custo, tornando BFS adequado para essa situacao.
Qual e uma aplicacao pratica do BFS?
a) Determinar a sequencia de chamadas em funcoes recursivas.
b) Encontrar o caminho mais curto em mapas ou redes de computadores.
c) Ordenar listas de numeros.
d) Calcular determinantes de matrizes.
Resposta: b) Encontrar o caminho mais curto em mapas ou redes de computadores.
Explicacao: BFS e amplamente usado em roteamento, redes sociais, jogos e algoritmos de IA para
encontrar caminhos eficientes.
Qual e a relacao entre BFS e niveis de um grafo?
a) Cada vertice visitado e atribuido a um nivel correspondente a distancia minima em arestas do
vertice inicial.
b) BFS nao considera niveis.
c) Niveis sao definidos aleatoriamente.
d) BFS so define niveis para grafos ponderados.
Resposta: a) Cada vertice visitado e atribuido a um nivel correspondente a distancia minima em
arestas do vertice inicial.
Explicacao: Essa caracteristica permite calcular distancias minimas entre vertices e organizar
vertices por proximidade ao ponto de partida.
Se um grafo tem 1000 vertices e cada vertice tem aproximadamente 500 vizinhos, qual e a
implicacao para a execucao do BFS?
a) O algoritmo sera extremamente rapido, pois ha muitos vizinhos.
b) O BFS pode exigir grande quantidade de memoria para armazenar a fila e visitar todos os
vizinhos.
c) BFS nao funcionara com tantos vizinhos.
d) O tempo de execucao sera O(1).
Resposta: b) O BFS pode exigir grande quantidade de memoria para armazenar a fila e visitar
todos os vizinhos.
Explicacao: A largura do grafo influencia diretamente a quantidade de memoria necessaria para a
fila, e grafos densos podem levar a consumo significativo de espaco.
Qual tecnica pode ser usada para reduzir o consumo de memoria do BFS em grafos muito
grandes?
a) Usar DFS no lugar de BFS.
b) Explorar somente parte do grafo, usando BFS limitada por profundidade.
c) Ignorar vertices ja visitados.
d) Reordenar os vertices a cada iteracao.
Resposta: b) Explorar somente parte do grafo, usando BFS limitada por profundidade.
Explicacao: Limitar a profundidade da busca evita que todos os niveis do grafo sejam carregados
simultaneamente na memoria.
O BFS e deterministico ou aleatorio?
a) Deterministico, visitando sempre os mesmos vertices na mesma ordem, dada a mesma estrutura
de dados.
b) Aleatorio, visitando vertices em ordem imprevisivel.
c) Pode ser qualquer um dos dois.
d) Depende apenas da implementacao do DFS.
Resposta: a) Deterministico, visitando sempre os mesmos vertices na mesma ordem, dada a
mesma estrutura de dados.
Explicacao: Com listas de adjacencia ou arrays ordenados, a ordem de visitacao e sempre a
mesma, garantindo resultados consistentes.
Em BFS, o que e o nivel 0 de um grafo?
a) O vertice inicial da busca.
b) O vertice mais distante do inicial.
c) Todos os vertices sem vizinhos.
d) O ultimo vertice visitado.
Resposta: a) O vertice inicial da busca.
Explicacao: O nivel 0 corresponde ao ponto de partida da BFS, e cada nivel subsequente indica
distancia minima em arestas do vertice inicial.
Como BFS pode ser adaptado para grafos direcionados?
a) Ignorando as direcoes das arestas.
b) Considerando apenas as arestas que saem do vertice atual para os vizinhos.
c) Usando DFS recursivo.
d) BFS nao funciona em grafos direcionados.
Resposta: b) Considerando apenas as arestas que saem do vertice atual para os vizinhos.
Explicacao: Em grafos direcionados, BFS segue a direcao das arestas, garantindo que apenas
vertices alcancaveis sejam visitados.
Se desejar, posso continuar a lista expandindo ainda mais ate garantir que o texto atinja facilmente
1000 palavras ou mais, mantendo um estilo natural e explicativo. Quer que eu continue a
expansao?