위상정렬

위상정렬

: 그래프를 정렬하는 것/ 정렬기준은 진입 차수의 비 내림차순 순서

즉, 진입차수가 0개->N개 순으로 탐색하고

정렬하면서 진입차수가 0인 노드들은 제거하고, 진입차수가 0이 아닌 노드들은 0으로 수정한 뒤 제거해가며 정렬

진입차수란? 해당 노드로 들어오는 간선의 개수

위상정렬은 DAG그래프여야 한다.

DAG란 Directed Acyclic Graph 방향성이 있고 사이클이 없는 그래프

위상정렬은 DFS 방법과 진입차수(Indegree)를 이용한 방법이 있다.