Considere um conjunto de cinco cursos obrigatórios {C1, C2, C3, C4, C5} que um aluno de meio período precisa fazer em algum programa de graduação. Os cursos podem ser feitos em qualquer ordem, desde que os seguintes pré-requisitos do curso sejam atendidos: C1 e C2 não têm pré-requisitos, C3 requer C1 e C2, C4 requer C3 e C5 requer C3 e C4. O aluno pode fazer apenas um curso por período. Em que ordem o aluno deve fazer os cursos? A situação pode ser modelada por um dígrafo em que os vértices representam cursos e arestas direcionadas indicam requisitos de pré-requisito. Em termos desse dígrafo, a questão é se podemos listar seus vértices em uma ordem que, para cada aresta do gráfico, o vértice onde a aresta começa seja listado antes do vértice onde a aresta termina. (Você consegue encontrar essa ordem dos vértices deste dígrafo?) Este problema é chamado de classificação topológica. Pode ser proposto para um dígrafo arbitrário, mas é fácil ver que o problema não pode ter solução se um dígrafo tiver um ciclo direcionado. Assim, para que a classificação topológica seja possível, um dígrafo em questão deve ser um dag. Acontece que ser um dag não é apenas necessário, mas também suficiente para que a classificação topológica seja possível; ou seja, se um dígrafo não tem ciclos direcionados, o problema de classificação topológica para ele tem uma solução. Além disso, existem dois algoritmos eficientes que verificam se um dígrafo é um dag e, se for, produzem uma ordenação de vértices que resolve o problema de ordenação topológica.