Questão de Algoritmos e Estrutura de Dados — Algoritmos — UECE-CEV 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg615404
Banca
UECE-CEV
Órgão
PGE-CE
Ano
2025
Nível
Médio
Cargo
Técnico de Representação Judicial - Tecnologia da Informação - Análise e Desenvolvimento de Sistemas
O algoritmo que é usado para resolver o problema encontrar uma árvore subjacente que conecte todos os vértices com o menor peso possível sem formar ciclos é o algoritmo de
ABellman-Ford.
BFloyd-Warshall.
CFord-Fulkerson.
DWarshall.
EKruskal.
Revelar gabarito e comentário▾
GabaritoE — Kruskal.
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”.
Algoritmos para Árvore Geradora Mínima
Gabarito: letra E. O enunciado descreve exatamente o algoritmo de Kruskal, que encontra uma árvore geradora mínima (MST) em um grafo ponderado, conectando todos os vértices com o menor peso total e sem formar ciclos. Os demais algoritmos têm finalidades distintas: caminhos mínimos (Bellman-Ford, Floyd-Warshall), fluxo máximo (Ford-Fulkerson) e fecho transitivo (Warshall).
Algoritmos em grafos: Árvore Geradora Mínima (MST) (Kruskal (arestas por peso, sem ciclo), Prim (vértices, sem ciclo)); Caminho mínimo (Bellman-Ford (peso negativo), Floyd-Warshall (todos os pares)); Fluxo máximo (Ford-Fulkerson); Fecho transitivo (Warshall)
Alternativa A — ❌ Incorreta
O algoritmo de Bellman-Ford é usado para encontrar o caminho mais curto de uma única fonte em grafos que podem conter arestas com peso negativo, não para árvore geradora mínima.
Alternativa B — ❌ Incorreta
Floyd-Warshall resolve o problema de todos os pares de vértices com caminhos mais curtos, não o problema de árvore geradora mínima.
Alternativa C — ❌ Incorreta
Ford-Fulkerson é um algoritmo clássico para fluxo máximo em redes de fluxo, não para encontrar árvores geradoras.
Alternativa D — ❌ Incorreta
O algoritmo de Warshall (ou Floyd-Warshall) é utilizado para fecho transitivo ou caminhos mínimos; não se aplica ao problema descrito.
Alternativa E — ✅ Correta ⟵ GABARITO
Kruskal é o algoritmo padrão para árvore geradora mínima. Ele ordena as arestas por peso crescente, adicionando-as ao conjunto da solução desde que não formem ciclo, até que todos os vértices estejam conectados. É a resposta correta.