Questão de Algoritmos e Estrutura de Dados — Algoritmos — COMPERVE - UFRN 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq430941
Banca
COMPERVE - UFRN
Órgão
UFRN
Ano
2019
Nível
Superior
Cargo
COMPERVE - - Engenheiro - Engenharia da Computação
O código abaixo pode ser utilizado para atravessar um grafo.Entrada: um gráfico G e um vértice v de GSaída: todos os vértices alcançáveis de v marcadosfunção DFS(G,v):marque vpara todas as arestas adjacentes a v, façase vértice w não estiver marcado, entãoChame recursivamente DFS(G,w)fim sefim parafim funçãoEntre os diversos tipos de algoritmos utilizados para atravessar grafos, esse código implementa o algoritmo
Abusca em profundidade ou Depth-First Search.
Bbusca em largura ou Breadth-First Search.
Cbusca melhor-primeiro ou Best-First Search
Dbusca exaustiva ou Brute-Force Search.
Revelar gabarito e comentário▾
GabaritoA — busca em profundidade ou Depth-First Search.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Busca em Profundidade (DFS) em Grafos
Gabarito: letra A. O pseudocódigo apresentado descreve exatamente o algoritmo de busca em profundidade (DFS – Depth-First Search): a partir de um vértice v, marca-o como visitado e, recursivamente, explora cada vértice adjacente não marcado. Essa estratégia de explorar o máximo possível antes de retroceder caracteriza a DFS, que utiliza implicitamente uma pilha (a pilha de chamadas recursivas).
A banca testa o reconhecimento da implementação clássica de DFS, em contraste com outros algoritmos de travessia de grafos.
Algoritmos de travessia em grafos: Busca em profundidade (DFS) (Pilha (recursão), Aprofunda antes de retroceder, ✅ Código dado); Busca em largura (BFS) (Fila, Visita por níveis, ❌ Código dado); Busca melhor-primeiro (Best-First) (Heurística, ❌ Código dado); Busca exaustiva (Brute-Force) (Testa todas as possibilidades, ❌ Código dado)
Alternativa A — ✅ Correta ⟵ GABARITO
O código é a implementação recursiva padrão da busca em profundidade (DFS). A DFS visita um vértice e, em seguida, segue recursivamente por cada aresta para vértices ainda não visitados, aprofundando-se antes de retroceder.
Alternativa B — ❌ Incorreta
A busca em largura (BFS – Breadth-First Search) utiliza uma fila para visitar os vértices por níveis (distância da origem). O pseudocódigo não usa fila nem visita por níveis; ele é recursivo, típico de DFS. A BFS seria implementada com uma fila explícita e um laço.
Alternativa C — ❌ Incorreta
A busca melhor-primeiro (Best-First Search) é um algoritmo heurístico que seleciona o próximo vértice com base em uma função de avaliação (por exemplo, distância estimada ao destino). O código dado não utiliza nenhuma heurística, apenas a marcação de vértices visitados.
Alternativa D — ❌ Incorreta
Busca exaustiva ou força bruta (Brute-Force Search) refere-se a testar todas as possibilidades sem estratégia específica. Embora a DFS também explore todo o grafo, o termo “busca exaustiva” é genérico e não denota o algoritmo particular implementado. O pseudocódigo é uma DFS clássica, não um mero “testar todas as opções” sem ordem definida.