POSCOMP 2019: Questão 37 Resolvida (Teoria dos Grafos)

Por
| 

Logotipo do POSCOMP 2019

Questão

Dado um grafo G e um vértice de origem, qual é o algoritmo de busca que descobre todos os vértices a uma distância K do vértice origem, antes de descobrir qualquer vértice a uma distância K+1?

  • (A) Pré-ordem.
  • (B) Largura.
  • (C) Pós-ordem.
  • (D) Profundidade.
  • (E) Simétrica.

Resolução

O algoritmo de busca que satisfaz as condições do enunciado é o algoritmo de busca em largura. Dado um vértice, o algoritmo irá fazer a busca em todos os vértices vizinhos desse vértice situados no mesmo nível e depois parte para o próximo nível.

A busca em largura começa por um vértice, digamos s, especificado pelo usuário. O algoritmo visita s, depois visita todos os vizinhos de s, depois todos os vizinhos dos vizinhos, e assim por diante (FEOFILOFF, 2019).

A busca em largura nos grafos funciona de maneira similar ao percurso em nível em árvores. Na prática, o percurso realizado pela busca em largura gera uma árvore cuja raiz é o vértice inicial e cada nível da árvore contém os nós/vértices que estão a uma mesma distância da raiz.

Portanto, a alternativa correta é a B.

Grafo com cidades da Alemanha
O grafo à esquerda contém algumas cidades da Alemanha e a distância entre elas. A árvore à direita é obtida a partir de uma busca em largura no grafo partindo do vértice que representa a cidade de Frankfurt (Fonte: Wikimedia Commons).

Mais questões

Se você deseja mais questões resolvidas do POSCOMP 2019, acesse a tag Questões do POSCOMP 2019.

Agora, se você procura questões, gabaritos e caderno de questões de outras edições, então acesse a página POSCOMP.

Resolverei as questões conforme o tempo permitir e de acordo com os meus conhecimentos. Como eu não sei resolver todas as questões, recomendo que você consulte também o gabarito oficial do exame.

Referências

FEOFILOFF, P. Busca em largura. São Paulo: IME-USP, 2019. Acesso em 18 de março de 2020.

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini. Qualquer valor doado contribui muito para a difusão do conhecimento.

Doar com PagSeguroDoar com PayPal


Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário