Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2024

Grafos Acíclicos Direcionados

Gabarito: letra A. Um grafo acíclico direcionado (DAG) é exatamente um grafo com arestas direcionadas que não contém nenhum ciclo direcionado, conforme descrito no enunciado. As demais alternativas referem-se a outros tipos de grafos que não correspondem à definição.

Alternativa A — ✅ Correta ⟵ GABARITO

Define corretamente um grafo acíclico direcionado (Directed Acyclic Graph – DAG). É um grafo onde as arestas têm direção e não há caminho fechado (ciclo) seguindo a orientação das arestas.

Alternativa B — ❌ Incorreta

Grafo simples é aquele que não possui arestas múltiplas nem laços, mas pode conter ciclos. A ausência de ciclos não é uma característica definidora de grafos simples.

Alternativa C — ❌ Incorreta

Grafo ponderado possui pesos (valores numéricos) associados às arestas, mas pode ou não ter ciclos. A definição do enunciado não menciona pesos.

Alternativa D — ❌ Incorreta

Grafo desconexo é aquele que possui pelo menos dois componentes conexos, ou seja, não é possível alcançar todos os vértices a partir de qualquer vértice. Isso não está relacionado à existência de ciclos direcionados.

Alternativa E — ❌ Incorreta

Grafo cíclico é justamente o oposto: possui ao menos um ciclo. O enunciado especifica a ausência de ciclos direcionados, portanto esta alternativa está em contradição direta.