Question

Uma empresa de logística transformou num grafo, o caminho interligando a sua matriz e todas as filiais, com o objetivo de aplicar algoritmos de busca em grafos, procurando melhor eficiência em suas rotas de entrega.

Considerando o grafo, a partir do vértice 2, como se daria a busca em largura até encontrar o vértice 3?

Answer 1

Resposta:

1 - 2, 5, 6, 1, 9, 10, 3.

Explicação:

Answer 2

A resposta correta para o algoritmo de busca em largura neste caso é a alternativa 1, ou seja, a ordem 2, 5, 6, 1, 9, 10, 3.

Dentre os algoritmos de busca utilizados para grafos, o método que a questão pede que utilizemos é a busca em largura. No método de busca em largura, começamos por um vértice raiz e varremos todos seus vértices vizinhos. Depois, para cada vértice já varrido, varremos novamente seus vizinhos e assim por diante.

Executando o algoritmo de busca em largura para grafos

• Se queremos encontrar o vértice 3, comecemos a busca pelos vértices vizinhos primeiro.
• Normalmente, tomamos a ordem de busca da esquerda para a direita.
• Portanto, partindo do vértice raiz 2, encontramos os vértices vizinhos 5, 6 e 1.
• Agora, buscamos os vértices de distância 2. Isto é, os vizinhos dos vizinhos.
• Encontraremos os vértices 9, 10 e, finalmente, o vértice 3.

Portanto, a ordem final será 2, 5, 6, 1, 9, 10, 3. Esta ordem é justamente a ordem na alternativa 1.

Veja mais sobre busca em largura em:

https://brainly.com.br/tarefa/21947977

#SPJ2