알고리즘은 다음과 같이 설명할 수 있습니다.
n개의 꼭지점과 m개의 모서리가 있는 유향 그래프가 주어집니다. 각 가장자리가 낮은 번호의 정점에서 높은 번호의 정점으로 이어지는 방식으로 정점의 번호를 다시 지정해야 합니다.
즉, 그래프의 모든 모서리에 의해 주어진 순서에 해당하는 정점의 순열(위상적 순서)을 찾아야 합니다.
깊이 우선 검색(dfs(v))
을 사용합니다.
\(dfs(v)\) 에서 종료할 때 목록의 시작 부분에 정점을 추가하면 끝 이 목록에서 토폴로지 정렬을 얻습니다.
따라서 원하는 토폴로지 정렬 — 종료 시간의 내림차순으로 정렬됩니다.