[알고리즘]위상정렬

위상정렬의 개념 위상정렬Topological Sort은 일의 순서가 있는 작업을, 순서에 맞게 정렬해주는 알고리즘 입니다. 대부분 우리가 하는 일에는 순서가 있습니다. 예를 들어 수육을 만들고, 상을 차리는 과정을 나타내면 아래와 같습니다. 위 그림을 보면 각 일의 순서가 있는 것을 알 수 있습니다. 고기를 넣으려면, 냄비에 물이채우고 가열을 해야함과 동시에, 고기가 손질되어 있어야 함을 알 수 있습니다. 이렇게 위상정렬은, 일의 순서 자체가 중요하기 때문에, 반드시 간선의 방향이 있어야 합니다. 이런 특성 때문에, 이전 배웠던 그래프 종류는 DAG가 되야 위상정렬을 할 수가 있습니다. 싸이클이 존재하거나 간선의 방향이 없으면 일의 방향이 명확하게 결정되지 않기 때문 입니다. 위상정렬의 과정 위상정렬에서 가장 중요한 것은 일의 순서가 있다는 것입니다. 위상정렬의 핵심동작은 아래와 같습니다. 먼저, 바로 진행할수 있는 일을 찾습니다. 자신을 향한 화살표가 없는 일의 경우엔, 사전작업이...

원문링크 : [알고리즘]위상정렬