위상 정렬이란? 위상 정렬이란 방향이 있는 비순환 그래프(DAG, Directed Acyclic Graph)에서 모든 노드를 방향성에 따라 순서대로 정렬하는 알고리즘이다.
즉, 모든 노드들을 자신을 가리키는 화살표가 있는 다른 노드보다 앞에 오도록 배열하는 것이다. 이 알고리즘은 그래프 내부의 우선순위가 있는 작업들을 수행하는 순서를 결정하기 위해 사용된다.
위상 정렬 알고리즘의 핵심은 진입 차수(in-degree)를 이용하는 것이다. 진입 차수는 어떤 노드로 들어오는 화살표의 수를 의미한다.
위상 정렬은 진입 차수가 0인 노드부터 처리하면서, 해당 노드에서 출발하는 모든 화살표를 제거하고, 그 화살표를 제거한 노드의 진입차수를 감소시킨다. 이러한 과정을 반복하여 모든 노드를 처리하는 순서를 구한다.
위.....
