Logo Passei Direto
Buscar

Concursos

Outros
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.
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 em relação ao algoritmo BFS (Busca em Largura) em um grafo ponderado: a) Sempre encontra o caminho de menor custo. - Esta afirmação é falsa. O BFS não considera os pesos das arestas, apenas a quantidade de arestas. b) Não garante o menor custo, apenas o menor número de arestas. - Esta afirmação é verdadeira. O BFS encontra o caminho com o menor número de arestas, mas não necessariamente o de menor custo em um grafo ponderado. c) Não pode ser executado. - Esta afirmação é falsa. O BFS pode ser executado em um grafo, independentemente de ser ponderado ou não. d) Funciona apenas se os pesos forem inteiros positivos. - Esta afirmação é falsa. O BFS pode ser executado independentemente dos pesos das arestas, mas não garante o menor custo. Portanto, a alternativa correta é: b) Não garante o menor custo, apenas o menor número de arestas.

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

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.

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)

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