![Logotipo do POSCOMP 2019](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpbASAxjtWstTJO8MBYmKR98dFSpNXn8KFAHae4qzxRiWj_4qHt5a2DdzXYu6dURGVXiQYrTWZ86M1ws6fIL2d3sBiz0iEjfbSqD_3ghib-NWOeiRO03iR6NXVO2PHxiopmhMx2UTiqVdx/s1600/poscomp-2019-questao-37.png)
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](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicK3Gm1QraxK8cMgectPovGt-Cxp1AymxhEcYcxpOXQJ20V98To6oIc_cZfboRXtvibbmMtYsSkdiKU53Qncm1ZcPuoy2kZkLF5TsEOJ9cgrirxDyHxBlIdNl6rJiUZQwmBqgcc0Ey_xfb/s1600/busca-em-largura-grafos-exemplo.png)
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.
Nenhum comentário:
Postar um comentário