Logo Passei Direto
Buscar

Concursos

Outros
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.
User badge image
Desenvolvendo com Questões

há 2 meses

User badge image
Desenvolvendo com Questões

há 2 meses

Busca em largura (BFS)
7 pág.

Busca em largura (BFS)

Respostas

User badge image

Ed Verified user icon

há 2 meses

Vamos analisar as alternativas sobre a propriedade do BFS (Busca em Largura) em um grafo não ponderado: a) Sempre encontra o caminho mais curto em termos de número de arestas entre dois vértices. - Esta afirmação é verdadeira. O BFS explora todos os vértices a uma certa distância antes de explorar os vértices a uma distância maior, garantindo que o primeiro caminho encontrado para um vértice seja o mais curto em termos de número de arestas. b) Pode encontrar caminhos mais longos antes dos curtos. - Isso não é verdade para o BFS, pois ele prioriza a exploração de caminhos mais curtos. c) Funciona apenas em grafos direcionados. - O BFS pode ser aplicado tanto em grafos direcionados quanto em grafos não direcionados. d) Sempre visita os vértices em ordem alfabética. - O BFS não garante uma ordem alfabética; ele visita os vértices com base na estrutura do grafo e na ordem em que são descobertos. Portanto, a alternativa correta é: a) Sempre encontra o caminho mais curto em termos de número de arestas entre dois vértices.

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Busca em largura (BFS)
7 pág.

Busca em largura (BFS)

Mais perguntas desse material

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.

Qual estrutura de dados e fundamental para a implementacao do BFS?
a) Pilha
b) Fila
c) Lista ligada
d) Arvore binaria

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!)

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)

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.

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.

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.

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.

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.

Mais conteúdos dessa disciplina