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

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.

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.